3 Replies - 546 Views - Last Post: 19 January 2013 - 04:22 PM Rate Topic: -----

#1 Heiland  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 11-January 13

Detecting duplicate numbers in an array

Posted 18 January 2013 - 11:41 PM

I am trying to detect duplicate numbers in an array. If there are duplicates then it should return false, but if each number in the list is different then it should return true. The problem it that it gives me either true or false for both cases. I know why it does this, which is because of the if statement on line 17, however I do not know what to do about it. If I take out the line 17 if statement then the problem simply shifts to another place in the code. The problem occurs when the two variables, index2 and endLine, are equivalent. My basic approach to the problem is to take the number at the 0th position in the array and compare it to the number in 1st position, then the 2nd, 3rd, 4th, and so on. I have called this constantly increasing variable index1 (that's index "one" not index "L"). When I reach the end of the array, meaning when index1 and endList are the same I set index1 to index2+1 so that it is always one position ahead in the list and repeat the loop. As I have stated previously, the problem occurs when index2 and endLine are the same. Any help or suggestions would be appreciated, sorry for the length of the description.

import java.util.Arrays;

public class DistinctCheck {
    public static boolean areDistinct(int[] a) {
        int index1=1;
        int index2=0;
        int endList=a[a.length-1];
        
        while(index2<=a.length){ 
            if(a[index1]==a[index2]){
                return false;
            }
            else if(endList==a[index1]){
                index2++;
                index1=index2+1;
                
                if((endList-index2)==1){
                    return true;
                }
            }
            else{
                index1++;
                
            }
        
       // FILL IN CODE HERE
    }
    return true;
}

    
    
    
    public static void printIntArray(int[] a) {
        System.out.println(Arrays.toString(a));
       // FILL IN CODE HERE
    }
    
    public static void main(String[] args) {
        int[] a1 = {1,2,3,4,5,6,7,8,9};
        System.out.println("First array is printed below: ");
        printIntArray(a1);
        System.out.println("areDistinct for first array: " + areDistinct(a1));
        
        int[] a2 = {1,3,5,7,6,4,3,2};
        System.out.println("Second array is printed below: ");
        printIntArray(a2);
        System.out.println("areDistinct for second array: " + areDistinct(a2));
    }
}


Please disregard my comment "FILL IN CODE HERE" that was a note to myself when I began.

Is This A Good Question/Topic? 0
  • +

Replies To: Detecting duplicate numbers in an array

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10392
  • View blog
  • Posts: 38,458
  • Joined: 27-December 08

Re: Detecting duplicate numbers in an array

Posted 18 January 2013 - 11:41 PM

I would just use a HashSet. Add all the elements in the array to the Set. If the Set's size() == array.length, then all the elements are distinct. This is an O(n) time solution.
Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Detecting duplicate numbers in an array

Posted 19 January 2013 - 11:12 AM

Don't have to go to the end and check the size
The add() method returns false if the element is already in the Set

boolean areDistinct(int[] array) {
    HashSet hs = new HashSet<Integer>(array.length);
    for(int i = 0; i < array.length; ++i) {
      if(!hs.add(array[i]))
         return false;
    }
    return true;
}



will probably be less than O(n) if there is duplicate :)/>

This post has been edited by pbl: 19 January 2013 - 11:16 AM
Reason for edit:: fixed unbalanced ()

Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10392
  • View blog
  • Posts: 38,458
  • Joined: 27-December 08

Re: Detecting duplicate numbers in an array

Posted 19 January 2013 - 04:22 PM

Still O(n), by definition. But you're right- definitely fewer than n steps. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1