Найти максимальное значение integer (Mode) в несортированном массиве

Question

Как найти максимальное число раз (режим) целого числа в несортированном массиве целых чисел?

Один O(nlogn) подход, который я мог придумать, это сортировать. Есть ли другой лучший подход?

Answer 1

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

так в псевдокоде:

hashtable hash; 
foreach(element in array){ 
    if(!hash.contains(element)) 
    hash[element] = 1; 
    else 
    hash[element]++; 
} 

int max = 0; 
max_element; 
foreach(element in hash) 
    if(hash[element] > max) 
    { 
    max_element = element; 
    max = hash[element]; 
    } 

//max_element contains the maximum occuring one. 

Answer 2

Если вы используете Linq вы можете сделать это

IEnumerable.Max(); 

Answer 3

Вы можете использовать хэш-таблицу с «номером в массиве» как ключ и «вхождение» в качестве значений.

Пример кода выглядеть так:

hashtable h; 
for every entry in array 
     search hashtable 
      if present, increment num_occurrences 
      else, create new entry 

Iterate over all the entries in hashtable and return one 
with max num_occurrences 

В поиске в хэш считается O (1), общая сложность будет O (п).

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

Возвращает индекс наибольшего значения в этом массиве.

Answer 4

Вот основной набросок того, что вы будете делать:

1. Сначала сортировать массив - O (п LOGN) упаковывают слияния рода
2. Declare Count = 1, MAX_COUNT = 1, max_value = arr [0]
3. Итерировать через массив, начиная с индекса 1
4. Сравнить каждый элемент с помощью предыдущего элемента. Обновление счета, MAX_COUNT, если они равны, то еще сбросить отсчитать назад к 1
5. возвращения MAX_COUNT, max_value

 
Time Complexity : O(n logn)+ O(n) 
Space Complexity : InPlace , no hash table or hash map is required. 

Вот код:

public void Max_Occurrence(int[] arr) 
{ 
    int count=1; 
    int max_count =1; 
    int max_value = arr[0]; 
    for(int i=1; i<arr.length ; i++) 
    { 
     if(arr[i-1] == arr[i]) 
     { 
      count++; 
      if(max_count<count) 
      { 
       max_count = count; 
       max_value = arr[i]; 
      } 
     } 
     else 
     { 
      count = 1;//changing from count++. As per the steps mentioned above it should be reset to count = 1. Suggested by an anonymous user 
     } 
    } 

    System.out.println("Result:"+max_value+" has occured "+max_count+"of times"); 
} 

Answer 5

Попробуйте это.

class max_frequency 
{ 
private int a[]=new int[20]; 
public void accept(int a1[]) 
{ 
    a=a1; 
} 
public void sort() 
{ 
    int i,j,t; 
    for(i=0;i<20;i++) 
    { 
     for(j=i+1;j<20;j++) 
     { 
      if(a[i]>a[j]) 
      { 
       t=a[i]; 
       a[i]=a[j]; 
       a[j]=t; 
      } 
     } 
    } 
    int count=1; 
    int max_count=1; 
    int max_value=0; 
    for(i=1;i<a.length;i++) 
    { 
     if(a[i-1]==a[i]) 
     { 
      count++; 
      if(max_count<count) 
      { 
       max_count=count; 
       max_value=a[i]; 
      } 
     } 
     else 
     { 
      count=1; 
     } 
    } 
     System.out.println("Result : "+max_value+ " has occured "+max_count+ " times"); 
} 

}