подсчет числа уникальных элементов

Question

Привет, поэтому я должен посчитать количество уникальных элементов после сортировки массива, исключая дубликаты, но я получаю неправильный вывод.

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); 

}}

ожидается выход: Java InstrumentedBinarySearch tinyW.txt < tinyT.txt

получили: 16

ли я подсчитать количество дубликатов или что нибудь?

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

Этот алгоритм подсчитывает, сколько различных уникальных чисел есть в массиве. Число, появляющееся более одного раза, будет учитываться только для 1. Я предполагаю, что это то, что вы имеете в виду, в отличие от «чисел, которые появляются ровно один раз».

Существует более тривиальный способ сделать это, как предлагается в другом ответе, но для этого требуется вложенный цикл for и, следовательно, выполняется в квадратичной сложности. Мой алгоритм ниже пытается решить проблему в линейном времени, пропорциональном размеру массива.

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++; 
    } 
} 

Например, учитывая массив:

{1,2,3} это даст 3, потому что есть 3 уникальные номера

{1,2,3,3,3, 4,4,4,5} это даст 5, потому что есть еще 5 уникальных номеров

Answer 3

Прежде всего, давайте посмотрим на ваш цикл:

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

Вы должны сравнивать последовательные элементы в списке, например белый список [0] == whitelist [1] ?, белый список [1] ​​== белый список [2] ?, белый список [3] == белый список [4] ?, и т. Д. Выполнение whitelist[i] == whitelist[count] не имеет смысла в этом контексте.

У вас есть два варианта:

a. Увеличивает ваш счетчик, когда вы найдете два последовательных элементы, которые равны и вычтут из общего размера массива:

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

б. Измените условие, чтобы подсчитать переходы между последовательными элементами, которые не равны. Так как вы подсчет количества переходов, вам нужно добавить 1 к count в конце концов, чтобы получить число уникальных элементов в массиве:

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

Обратите внимание, что в обоих случаях мы цикл только до whitelist.length - 1, так что whitelist[i + 1] не выходит за пределы.