Enthält Duplicate warum dieser Code Stack-Over-Flow?

Question

Hier ist das Problem: Geben Sie ein Array von Ganzzahlen, finden Sie, wenn das Array Dubletten enthält. Ihre Funktion sollte true zurückgeben, wenn mindestens ein Wert zweimal im Array erscheint, und sie sollte false zurückgeben, wenn jedes Element verschieden ist.

Hier ist mein Code, aber es ist ein Fehler, Stack-Überlauf:

public static class Solution { 
    public boolean containsDuplicate(int[] nums) { 
     if (nums.length < 1) 
      return false; 
     return recursion(nums, 0, nums.length - 1); 
    } 

    private static boolean recursion(int[] nums, int start, int end) { 
     if ((end - start) == 0) { 
      return true; 

     } 

     if ((end - start) == 1) { 
      if (nums[start] == nums[end]) { 
       return false; 
      } else { 
       return true; 
      } 
     } 
     boolean first = recursion(nums, start, (end - start)/2 - 1); 
     boolean second = recursion(nums, (end - start)/2, end); 

     if (first == false || second == false) { 
      return false; 
     } 
     return true; 
    } 
} 

Answer 1

Sie stattdessen eine HashSet schaffen könnte und die Prüfung ist der Schlüssel hat vor

public boolean containsDuplicate(final int[] nums) 
{ 
    Set<Integer> set = new HashSet<Integer>(); 
    for (int i : nums) { 
    if (set.contains(i)) return true; 
    set.add(i); 
    } 
    return false; 
} 

Answer 2

Dieses existiert line: boolean second = Rekursion (nums, (end - start)/2, end);

insbesondere folgende: (end - start)/2

Beispiel:

mit start = 0 end = 3

1. (3 - 0)/2 = 1

2. (3 - 1)/2 = 1

3. ...

Start wird immer gleich sein.

Das gleiche Verhalten wird mit der ersten Rekursion, außer Start bei 0 blockiert wird

Answer 3

ich Ihre Fehler reproduziert durch den Code auf meiner Seite ausgeführt wird - das Problem ist, dass recursion(nums, start, (end - start)/2 - 1) zu einem Punkt, an dem Index starten = 2 und der Endindex ist -3 - die Rekursion stoppt daher nie. Hier

ist die Korrektur - ich habe es gegen einen Array wie folgt getestet: int[] nums = new int[]{1,2,3,4,5,6,6};

private static boolean recursion(int[] nums, int start, int end) { 

     if((end - start) == 0){ return false;} 

     if((end - start) == 1){    
      //This is really where the recursion should end...unless if there were no duplicate, in which case we repeat 
      if(nums[start] == nums[end]){ 
       return true; 
      } 
      else{ 
       //we checked all against the first number - now we move the start to the next item on list 
       //so our new START is (start+1) and our new END (length-1) 
       return recursion(nums, (start+1), (nums.length-1)); 
      } 
     } 
     else{ 
      if(end < 0){return false;} 

      //here you evaluate if the start and end numbers are different 
      if(nums[start] == nums[end]){return true;}   
      return recursion(nums, start, (end - 1));   
     }  

    } 

Bitte ersetzen Sie „Rekursion“ -Funktion mit dem Code oben und mal sehen, ob es für Sie arbeitet.