counting number of unique elements

Question

Hi so I am supposed to count the number of unique elements after an array sort excluding duplicates but i'm getting the wrong output.

In in = new In(args[0]);
int[] whitelist = in.readAllInts();
Arrays.sort(whitelist);

int count = 0;
   for (int i = 0; i < whitelist.length; i++) {
       if (whitelist[i] == whitelist[count]) {
           count++;
       }
   }
while (!StdIn.isEmpty()) {
    int key = StdIn.readInt();
    rank(key, whitelist);
}
   System.out.println(count);

} }

expected output: java InstrumentedBinarySearch tinyW.txt < tinyT.txt

65

got: 16

Did i count the number of duplicates or something?

Answer 1

  int flag = 0;
  int count = 0;
       for (int i = 0; i < whitelist.length; i++) //Element to be checked for
  {
           for (int j=0; j< whitelist.length ; j++) //Loop that goes through the whole array 
       {
               if (whitelist[i] == whitelist[j]) //checks if there are duplicates
               {
                   flag++; // count
               }
       }
    if( flag==1) //There should be only 1 instance of the element in the array and that is the element itself
    { 
       System.out.println(whitelist[i]); //displays unique element
       count++; // Keeps count 
    }
 }

Answer 2

This algorithm counts how many different unique numbers there are in the array. A number appearing more than once will only count for 1. I am assuming this is what you mean, as opposed to "numbers which appear exactly once".

There is a more trivial way to do it, as proposed in another answer, but it requires a nested for-loop and therefore executes in quadratic complexity. My algorithm below attempts to solve the problem in linear time proportional to the array size.

int uniquesFound = 0;

// Assume that array is sorted, so duplicates would be next to another.
// If we find duplicates, such as 12223, we will only count its last instance (i.e. the last '2')
for (int i = 0; i < whitelist.length; i++) {

    // If we are at the last element, we know we can count it
    if (i != whitelist.length - 1) {
        if (whitelist[i] != whitelist[i+1]) {
            uniquesFound++;
        }
        else {
            // Nothing! If they are the same, move to the next step element
        }
    } else {
        uniquesFound++;
    }
}

For instance, given the array:

{1,2,3} this will yield 3 because there are 3 unique numbers

{1,2,3,3,3,4,4,4,5} this will yield 5 because there are still 5 unique numbers

Answer 3

First let's take a look at your loop:

for (int i = 0; i < whitelist.length; i++) {
    if (whitelist[i] == whitelist[count]) {
        count++;
    }
}

You should be comparing consecutive elements in the list, like whitelist[0] == whitelist[1]?, whitelist[1] == whitelist[2]?, whitelist[3] == whitelist[4]?, etc. Doing whitelist[i] == whitelist[count] makes no sense in this context.

Now you have two options:

a. Increment your counter when you find two consecutive elements that are equal and subtract the result from the total size of the array:

for (int i = 0; i < whitelist.length - 1; i++) {
    if (whitelist[i] == whitelist[i + 1]) {
        count++;
    }
}
int result = whitelist.length - count;

b. Change the condition to count the transitions between consecutive elements that are not equal. Since you are counting the number of transitions, you need to add 1 to count in the end to get the number of unique elements in the array:

for (int i = 0; i < whitelist.length - 1; i++) {
    if (whitelist[i] != whitelist[i + 1]) {
         count++;
    }
}
int result = count + 1;

Note that, in both cases, we loop only until whitelist.length - 1, so that whitelist[i + 1] does not go out of bounds.