在一个未排序的数组中找到出现最多的整数（众数）

Question

如何在未排序的整数数组中找到出现次数最多的整数（众数）？

我能想到的一种O(nlogn)方法是进行排序。是否还有其他更好的方法？

- Rajendra Uppal

Answer 1

以下是您需要做的基本概述：

1. 首先对数组进行排序-O(n logn)在合并排序的情况下
2. 声明Count=1，Max_Count=1，Max_Value=arr[0]
3. 从索引1开始遍历数组
4. 将每个元素与前一个元素进行比较。如果它们相等，则更新计数、Max_Count，否则将计数重置为1
5. 返回Max_Count、Max_value

时间复杂度：O(n logn)+ O(n)
空间复杂度：InPlace，不需要哈希表或哈希映射。

以下是代码：

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

- CoooolllYuvee

Answer 2

我认为您想要找到数组中出现次数最多的元素 - 如果您不关心内存，可以遍历一次数组，在哈希表中增加每个元素的计数。然后找到计数最高的元素。您需要遍历数组一次和哈希表一次。

因此，伪代码如下：

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.

- Axarydax

---

如果有一千万个整数，而且我当然不想使用额外的一千万个整数空间，那该怎么办呢？ - Rajendra Uppal

@Rajendra，您可能想使用哈希表来创建键，而不是使用数组索引作为键。哈希表使用哈希函数来创建键。 - sud03r

@Neeraj 好的，同意。你对以下情况有什么看法？

1. 一千万个整数的数组。
2. 只有一个重复的数字（我们的答案）。
3. 其余的（一千万减二）都是不同的整数。

- Rajendra Uppal

@Rajendra，你可以使用大小为2*1000万的数组，使用哈希函数对条目进行哈希处理，通过线性探测或分离链接避免冲突，并按照所述的方式继续进行。此外，如果数组中数字的范围很小，你可以进一步扩展Axarydax演示的方法，使用(element - min)代替element。 - sud03r

Answer 3

如果你正在使用 Linq，你可以这样做

IEnumerable.Max();

- Chris

---

亲爱的朋友们，我知道这个问题，请阅读我的评论，关于Younes的回答。我可以自己编写一个模板函数，从int、float、double或long类型的数组中找到最小值和最大值。 - Rajendra Uppal

Answer 4

你可以使用哈希表，以“数组中的数字”作为键，以“出现次数”作为值。

示例代码如下：

 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(n)。

这个问题的一个特殊情况是当数组中的数字在给定范围内时，在这种情况下，取另一个具有原始数组中最大值大小的int数组，并使用新数组的索引作为键，存储在该数组中的数字作为出现次数。

返回该数组中最大值的索引。

- sud03r

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

}

- Pranaya Prakash