Beste Weg zu finden, die Anzahl der Paare in einem array, dessen Differenz ist k

War ich der Lösung des Problems auf hackerrank. Ich hatte zwei Ansätze in meinem Kopf :

input : unsortierter array(a) und k

Erster Ansatz :

1) Sortieren Sie das array

2) für jedes array-element a[i] ,suchen Sie nach dem element a[i]+K unter Verwendung der binären Suche.Wenn gefunden increament der Graf und break die innere Schleife.

Zweiter Ansatz :

1) Sortieren Sie das array

2) für jedes array-element a[i] ,suchen Sie nach dem element a[i]+K mit linearsearch.Wenn gefunden increament der Graf und break die innere Schleife.

Fand ich den Ersten Ansatz besser zu sein, als es das problem zu lösen in n(logn). Aber wenn mehrere test-Fälle sind auf die Lösungen der Ansatz 2 nimmt weniger Zeit . Kann jemand bitte erklären, warum ?

Unten sind die Codes für die beiden Ansätze :

Ersten Ansatz Code :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    int beg;
    int mid;
    int end;
    int midVal;
    Arrays.sort(a);
    for(int i=0;i<len-1;i++){
    temp=a[i]+k;
    beg=i+1;  
    end=len-1;
        for(int l=beg;l<len;l++){
            mid=(beg+end)/2;
            midVal=a[mid];
            if(midVal==temp){
                count++;
                break;
            }
            else if(midVal>temp){
                end=mid-1;
            }
            else{
                beg=mid+1;
            }
        }

    }
    return count;
}

Zweite Ansatz Code :

static int pairs(int[] a,int k) {
  /* Complete this function */
    int temp;
    int len=a.length;
    int count=0;
    Arrays.sort(a);
    for(int i=0;i<len;i++){
    temp=a[i];
        for(int j=i+1;j<len;j++){
            if(temp-a[j]==-k){
                count++;
                break;
            }
        }
    }
    return count;
}

Duplizieren: Hier ist der beste Ansatz stackoverflow.com/questions/4720271/...

InformationsquelleAutor Sahil Gupta | 2013-11-24

6

Der erste Ansatz ist der beste hier unter den beiden, aber es ist der bessere Ansatz als die beiden:-

Hier ein pseudo-code für eine bessere Lösung:-
```
for(i=0;i<Arr.length;i++) {
  Hashmap.add(Arr[i])
}
count=0;
for(j=0;j<Arr.length;j++) {

  if(Hashmap.containsKey(Arr[j]+k))
     count++;

}
```
Zeit-Komplexität: O(N)
in der Erwägung, dass Ihr Ansatz = O(NlogN)

Edit:-

Hinweis:- Mein Ansatz hat mehr Platz-Komplexität von O(N) für die Hash-Tabelle in der Erwägung, dass vorgeschlagene Ansatz ist inplace.

Dies ist ein guter Ansatz. Sie sollten auch erwähnen, dass es ein besserer Ansatz, wenn der Speicher ist nicht ein Problem, da es unbedingt erforderlich wäre O (n) zusätzlichen Raum, während die anderen Lösungen umgesetzt werden können.
U Recht ich mache immer Platz-Komplexität Analyse, sondern verpasste dieser Zeit. Überprüfen Sie meine zu Bearbeiten.
Sieht gut aus 🙂 +1
Es gibt keine add() in HashMap
Ja, dass ist der Grund, warum ich angegeben haben, ist es eine pseudo-code.

InformationsquelleAutor Vikram Bhat
0

In deinem 1. code, deine innere Schleife, Abbruchbedingung ist falsch. Es sollte zu kündigen, wenn der beg und end Zeiger kreuzen.

Ändern while (beg <= end) oder for (; beg <= end; )

Auch für den zweiten Ansatz gibt es keine Notwendigkeit für die Sortierung des Arrays.

Im zweiten Fall, obwohl die Sortierung nicht tatsächlich helfen bei der Verringerung der Ordnung des Algorithmus, aber es könnte helfen, reduzieren einen erheblichen Mehraufwand in der linear-scan, wenn der Wert von k klein ist. Natürlich schlimmsten Fall führen beide das gleiche.
durch Ihre Logik, was passieren würde, wenn die Differenz groß ist?
Falls ich das nicht mit dem Sortieren für Ansatz 2 .Dann muss ich suchen-temp - -a[j]==-k und temp-a[j]==k , so dass für diesen mehr oder weniger die Zeit-Komplexität O(n^2). Während, wenn ich Sortiere das array zuerst die Laufzeit für mehrere Testfälle werden weniger.
wenn Sie die Durchführung einer linearen Suche, dann die Zeit-Komplexität für jeden Testfall werden O (n^2), ob das array sortiert ist.
Danke abhishek für die Antworten 🙂

InformationsquelleAutor Abhishek Bansal

Können Sie auch verwenden, legen Sie keine Notwendigkeit zu verwenden hashmap

public static void main(String[] args) throws Exception {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    int[] firstLine = Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int count = firstLine[0];
    int diff = firstLine[1];           
    Set<Integer> numbers = new HashSet<Integer>(Stream.of(in.readLine().split(" ")).map(Integer::valueOf).collect(Collectors.toList()));

    int pairCount = 0;
    for (Integer number : numbers) {
        pairCount += (numbers.contains(number+diff) ? 1:0); 
    }
    System.out.println(pairCount);                
}

InformationsquelleAutor fatih tekin

private static int CountDistinctPairs(int[] nums, int k) {
    //TODO Auto-generated method stub
    HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
    HashSet<String> set = new HashSet<String>();
    for(int i =0;i < nums.length;i++){
        map.put(nums[i],true);
    }
    for (int i = 0 ; i < nums.length; i++){
        if(map.containsKey(nums[i]+k)){
            String a = "";
            if(nums[i]<nums[i]+k){
                a = "("+nums[i]+","+(nums[i]+k)+")";
            }
            else{
                a = "("+(nums[i] + k)+","+nums[i]+")";
            }
            set.add(a);
        }
    }
    System.out.println(set);
    return set.size();
}

InformationsquelleAutor Saif ali Karedia

static boolean checkDuplicatesWithinK(int arr[], int k)
    {
        //Creates an empty hashset
        HashSet<Integer> set = new HashSet<>();

        //Traverse the input array
        for (int i=0; i<arr.length; i++)
        {
            //If already present n hash, then we found 
            //a duplicate within k distance
            if (set.contains(arr[i]))
               return true;

            //Add this item to hashset
            set.add(arr[i]);

            //Remove the k+1 distant item
            if (i >= k)
              set.remove(arr[i-k]);
        }
        return false;
    }

public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 4, 3, 5, 6};
        if (checkDuplicatesWithinK(arr, 3))
           System.out.println("Yes");
        else
           System.out.println("No");
    }

könntest du eine Erklärung zu diesem code? verbessern Sie Ihre Antwort, und, um zu helfen, die künftigen Leser

InformationsquelleAutor Deepak Maddeshiya

Meine Lösung

System.aus.println("findPair:"+findPair(new int[]{4,7,1,2,5,3,0,7,8,5,2}, 3));

public static int findPair(int[] nums, int target){ 
    Arrays.sort(nums);

    int count = 0;
    String pairText = "";
    for(int i =0; i < nums.length;i++){
        for(int j =i+1; j < nums.length;j++){

            if(nums[j]-nums[i] == target && (!pairText.equals(nums[i]+", "+nums[j]))){

                //System.out.println(nums[i]+", "+nums[j]);
                pairText = nums[i]+", "+nums[j];
                count++;
            }
        }

    }  


    return count;


}

InformationsquelleAutor Wei-Hsuan Chou

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.