Как мне найти три наиболее распространенных элемента в массиве? Я работаю с массивом длиной 10 000 с элементами = случайное целое число от 0 до 100.
Я думал об использовании двух массивов, один из которых имеет длину 100 и просто увеличивается с помощью оператора if. Однако мне было интересно, есть ли способ, которым можно было бы использовать только один цикл for/if (оператор) для поиска этих значений.
Если вы собираетесь делать это за постоянное число проходов по списку, вам понадобится вторая структура данных.
Если у вас есть нижняя и верхняя границы для значений в этом наборе и значения относительно плотные, то хорошим решением будет массив счетчиков.
В противном случае лучше использовать Map<Integer, Integer>, где ключи — это элементы множества, а значения — счетчики.
Анализ
Если у вас нет нижних/верхних границ в наборе перед началом, то вы не знаете большой массив счетчиков для выделения. Итак, вам нужно сделать предварительный проход по массиву, чтобы найти границы... и теперь у вас есть решение с двумя проходами.
Если у вас есть нижняя и верхняя границы, но набор разрежен, то стоимость инициализации массива счетчиков + стоимость нахождения трех самых больших счетчиков будут доминировать над стоимостью подсчета элементов набора. Если разница достаточно велика (т. е. ввод большой и очень разреженный), HashMap будет быстрее и займет меньше памяти.
В качестве альтернативы
Если вам разрешено изменять массив, вы можете отсортировать его в порядке возрастания O(NlogN), а затем найти три наиболее часто встречающихся элемента за один проход по отсортированному массиву.
Вы можете сделать это в одном цикле, но я думаю, что вам все еще нужен этот второй массив.
т.е. перебирайте свой входной массив, и каждый раз, когда вы видите значение, вы увеличиваете соответствующий индекс в своем массиве счетчиков. Но также сохраните 3 «верхних» индекса (отсортированных). Каждый раз, когда вы увеличиваете, проверяйте новое значение по сравнению со значением в трех верхних индексах, учитывая тот факт, что вы можете иметь дело с простым изменением порядка списка «верхних» значений.
Вероятно, есть лучшие способы сделать это, но это способ. Я только что напечатал массив режимов, но вы можете отсортировать его, чтобы увидеть, какое число встречается чаще всего. Это просто, потому что мы знаем верхнюю и нижнюю границы чисел, с которыми мы возимся, но если вы не знаете этих границ, вам нужно последовать совету, который дал Стивен С.
public class Main {
public static void main(String[] args) {
int i;
int value;
//one greater than max value because Math.random always returns a value less than 1.0
//this number also works good for our mode array size
int maxValue = 101;
int[] originalArray = new int[10000];
int[] modeArray = new int[maxValue];
for(i = 0; i < originalArray.length; i++){
value = (int) (Math.random() * maxValue);
originalArray[i] = value;
}
for(i = 0; i < originalArray.length; i++){
modeArray[originalArray[i]] += 1;
}
for(i = 0; i < modeArray.length; i++){
System.out.println("Number " + i + " occurred " + modeArray[i] + " times");
}
}
}
//find majority of a value in a array — O(n log n) -> wrost case O(n)
void findMajority(){
//sort
sort(begin(sarray),end(sarray));
//sarray[0] is our first number already counted
int cont=1;
int leader = sarray[0];
//temp variables to know when we changed to a different number
int tempLeader=0;
int tempCont=0;
//loop through sarray.size()
for(unsigned int i=1; i<size; i++){
if(tempLeader!=sarray[i]) //if we changed number tempCont is 0
tempCont=0;
if(sarray[i]==leader){ //if the current number in the array is our leader then keep counting
cont++;
}
else{ //if not, then our new number will be tempLeader and we count that one
tempLeader=sarray[i];
tempCont++;
if(tempCont>cont){ //its not higher occurences than our last number? skip, else we got a new leader
leader=tempLeader;
cont=tempCont;
tempLeader=0;
tempCont=0;
}
}
}
cout << "leader is" << leader << endl;
}
извините, это дерьмовое решение, но оно работает, как вы просили, надеюсь, это поможет
