1 2 Previous Next 22 Replies Latest reply on Oct 11, 2008 7:05 PM by 800282

    Checking if all numbers in int[] are unique

    843785
      Hi, I want to check if all the numbers in the int[] are unique. I have created this boolean method. It should return true if all of them are unique. Else, it should return false. But, it returns true all the time!
      public static boolean uniqueDigits(int[] numAr){
                boolean result = false;
                int num=0;
                int num1 = 0;
                int i=0;
                int j=0;
                while(i<numAr.length & j<numAr.length & i+j<numAr.length){
                          num = numAr;
                          num1 = numAr[i+j];
                          if (num == num1){
                               result = false;
                          }
                          else{
                               result = true;
                          }
                          i++;
                          j++;
                          }
                System.out.print(result);
                return result;
           }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
        • 1. Re: Checking if all numbers in int[] are unique
          mlk
          Add to the System.out.print to see the values of i, j, num1 and num2.

          Personally find the logic you are using rather confusing, but maybe I'm being thick.
          • 2. Re: Checking if all numbers in int[] are unique
            795402
            I'd use a nested for loop, checking every number (int n) in the array against all numbers to the right of n (n+1). If there's a match anywhere, you've found two identical numbers, hence return false.
            Makes for much less confusing code. And less code overall.
            • 3. Re: Checking if all numbers in int[] are unique
              801489
              I might be wrong because I am very sleepy, but I see that
              i = 0 and
              j = 0

              so wouldnt num = numAr[i] be num = numAr[0]
              and num1 = numAr[i+j] be num1 = numAr[0]

              Wouldn't a nested loop or just simply i+1 work more efficiently
              • 4. Re: Checking if all numbers in int[] are unique
                843785
                    public static boolean uniqueDigits(int[] numAr){
                        boolean result = true;
                        int i=0;
                        int j;
                        while(result && i<numAr.length-1) {
                            j=i+1;
                            while(result && j<numAr.length) {
                               result = numAr!=numAr[j];
                j++;
                }
                i++;
                }
                return result;
                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                • 5. Re: Checking if all numbers in int[] are unique
                  843785
                  oscarjustesen
                  I don't understand. How can I do that?
                  • 6. Re: Checking if all numbers in int[] are unique
                    baftos
                    Alternative: Arrays.sort() it, loop once through it to see if two neighbors are equal.

                    Edited by: baftos on Oct 11, 2008 10:31 AM
                    • 7. Re: Checking if all numbers in int[] are unique
                      843785
                      PaulRichards,
                      Thanx alot
                      • 8. Re: Checking if all numbers in int[] are unique
                        795402
                        public class UniqueDigits {
                             public static boolean uniqueDigits(int[] numbers) {
                                  for (int i = 0; i < numbers.length; i++) {
                                       for (int j = i + 1; j < numbers.length; j++) {
                                            if (numbers[i] == numbers[j]) { // We found two identical numbers.
                                                 return false;
                                            }
                                       }
                                  }
                                  return true; // No identical numbers found.
                             }
                             
                             public static void main(String args[]) {
                                  int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
                                  System.out.println("Numbers are " + (uniqueDigits(numbers) ? "unique" : "not unique"));
                             }
                        }
                        • 9. Re: Checking if all numbers in int[] are unique
                          843785
                          oscarjustesen wrote:
                          <A very inefficient comparison loop>
                          That's a whole lot of unnecessary looping. The same sort of logic can be more efficiently applied with far fewer comparisons::
                               public static boolean uniqueDigits(int[] numbers) {
                                    for (int i = 1; i < numbers.length; i++) {
                                         if (numbers[i] == numbers[i - 1]) return false;
                                    }
                                    return true; 
                               }
                          ~
                          • 10. Re: Checking if all numbers in int[] are unique
                            843785
                            I can think of several other ways to solve this problem. Here is my original solution:
                                public static boolean uniqueDigitsA(int[] numAr){
                                    boolean result = true;
                                    int i=0;
                                    int j;
                                    while(result && i<numAr.length-1) {
                                        j=i+1;
                                        while(result && j<numAr.length) {
                                           result = numAr!=numAr[j];
                            j++;
                            }
                            i++;
                            }
                            return result;
                            }
                                
                                Or, you can use a set:
                            public static boolean uniqueDigitsB(int[] numAr){
                            boolean result = true;
                            HashSet<Integer> set = new HashSet<Integer>();
                            int i=0;
                            while(result && i<numAr.length) {
                            result = !set.contains(numAr[i]);
                            set.add(numAr[i]);
                            i++;
                            }
                            return result;
                            }
                                
                                Or, a bit set:
                            public static boolean uniqueDigitsC(int[] numAr){
                            boolean result = true;
                            BitSet set = new BitSet();
                            int i=0;
                            while(result && i<numAr.length) {
                            result = !set.get(numAr[i]);
                            set.set(numAr[i]);
                            i++;
                            }
                            return result;
                            }
                                
                                Or, you could sort the array:
                            public static boolean uniqueDigitsD(int[] numAr){
                            int[] sorted = Arrays.copyOf(numAr, numAr.length);
                            Arrays.sort(sorted);
                            boolean result = true;
                            int i=0;
                            while(result && i<sorted.length-1) {
                            result = sorted[i]!=sorted[i+1];
                            i++;
                            }
                            return result;
                            }
                            If performance is critical and you are working with large (i.e. long) arrays, and the numbers do tend to be unique, then you might consider using uniqueDigitsC or uniqueDigitsD since I have found that they are faster.  However, for everyday usage I think uniqueDigitsA is fine :).
                            
                            Edited by: PaulRichards on Oct 11, 2008 7:54 AM                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                            • 11. Re: Checking if all numbers in int[] are unique
                              795402
                              And what if the array looks like this?
                              int[] numbers = { 1, 2, 1, 4, 5, 6, 7, 8, 9, 10 };
                              All numbers are not unique (numbers[0] and numbers[2] are both 1, but the method will return true.

                              Every number in the array needs to be compared with every other number in the array. Unless, of course, if you sort the array first.
                              • 12. Re: Checking if all numbers in int[] are unique
                                843785
                                oscarjustesen wrote:
                                And what if the array looks like this?
                                See reply #6; it assumes a sorted array. Sorry I wasn't more explicit about that.

                                ~
                                • 13. Re: Checking if all numbers in int[] are unique
                                  788165
                                  yawmark wrote:
                                  oscarjustesen wrote:
                                  <A very inefficient comparison loop>
                                  That's a whole lot of unnecessary looping. The same sort of logic can be more efficiently applied with far fewer comparisons::
                                       public static boolean uniqueDigits(int[] numbers) {
                                            for (int i = 1; i < numbers.length; i++) {
                                                 if (numbers[i] == numbers[i - 1]) return false;
                                            }
                                            return true; 
                                       }
                                  ~
                                  That will only recognize duplicates if they happen to be "next" to each other.
                                  • 14. Re: Checking if all numbers in int[] are unique
                                    843785
                                    LazarusLong wrote:
                                    That will only recognize duplicates if they happen to be "next" to each other.
                                    Right. See replies #6 and #12. I thought the operative assumption at the time of this discussion was that the array was sorted, especially given oscar's example code. If that's not the assumption, of course it won't work, and you'd want something of the sort (haha):
                                    public static boolean uniqueDigits(int[] digits) {
                                         int[] numbers = digits.clone();
                                         Arrays.sort(numbers);
                                         for (int i = 1; i < numbers.length; i++) {
                                              if (numbers[i] == numbers[i - 1]) return false;
                                         }
                                         return true; 
                                    }
                                    ~
                                    1 2 Previous Next