Наиболее распространенные значения в массиве

Question

Как мне найти три наиболее распространенных элемента в массиве? Я работаю с массивом длиной 10000 с элементами = случайное целое число от 0 до 100.

Я думал использовать два массива, один из 100 и просто увеличивая с помощью оператора if. Тем не менее, мне было интересно, существует ли способ, которым можно было бы использовать только один для цикла if (statement) для определения этих значений.

Answer 1

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

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

В противном случае лучше использовать Map<Integer, Integer>, где ключи являются элементами набора, а значениями являются счетчики.

Анализ

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

Если у вас есть нижняя и верхняя границы, но набор разрежен, тогда стоимость инициализации массива счетчиков + стоимость поиска трех крупнейших счетчиков будет доминировать над стоимостью подсчета установленных элементов. Если разница достаточно велика (т. Е. Вход большой & очень разреженный), HashMap будет быстрее и займет меньше памяти.

Альтернативно

Если разрешено изменить массив, вы можете отсортировать его в порядке возрастания O(NlogN), а затем найти три наиболее распространенных элементов в одном проходе через отсортированный массив.

Answer 2

Вы можете сделать это за один цикл, но я думаю, что вам все еще нужен этот второй массив.

I.e. петля над вашим массивом ввода, и каждый раз, когда вы видите значение, вы увеличиваете соответствующий индекс в массиве 'counter'. Но также сохраняйте 3 'верхние' индексы (отсортированные). Каждый раз, когда вы увеличиваете, проверьте свое новое значение на значение в верхнем индексе 3, учитывая тот факт, что вы можете просто переупорядочить свой список «верхних» значений.

Answer 3

Есть, вероятно, лучшие способы сделать это, но это способ. Я просто напечатал массив режимов, но вы можете отсортировать его, чтобы узнать, какое количество фактически произошло больше всего. Это просто, потому что мы знаем верхнюю и нижнюю границы чисел, с которыми мы возимся, но если вы не знаете этих границ, вам нужно взять совет, который дал Стивен C.

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

    } 

} 

Answer 4

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

жаль, его дерьмовый решение, но оно работает, как вы спросили, надеюсь, что это помогает