arrays - 在未排序的数组中查找最大出现整数 (Mode)

Question

如何在未排序的整数数组中找到出现最大次数(众数)的整数？

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

Answer 1

以下是您将要做的事情的基本概述:

1. 首先对数组进行排序 - O(n logn) incase of merge sort
2. 声明 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.

Here is the code:

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