元素在数组中重复的最大次数

Question

我需要一个算法，它返回给定整数数组中元素重复自身的最大次数。我需要它的线性时间复杂度，在最坏的情况下为 O(n)，而不使用

HashMap

。这可能吗？

static int maxR(int []arr) { 

    // using moore's voting algorithm 
    int n = arr.length;
    int res = 0; 
    int count = 1;
    int counter = 0;
    for(int i = 1; i < n; i++) { 
        if(arr[i] == arr[res]) { 
            count++; 
        } else { 
            count--; 
        } 
        if(count == 0) { 
            res = i; 
            count = 1; 
        } 
    } 
    for(int i = 0; i < n; i++) { 
        if(arr[i] == arr[res]) { 
            counter++; 
        } 
    } 
    return counter; 
} 

我尝试了这段代码，但它并不总是有效。对于此输入：

int arr[] = {40,50,30,40,50,30,60};

它给出了错误的答案。

Answer 1

你的代码甚至没有意义。你需要调试它。显然你不知道这是如何运作的。这并不太难：调试是手动遍历代码并将其与系统实际执行的操作进行比较的行为（使用调试器进行检查，或者如果必须的话，使用大量 System.out 语句进行检查）。交叉检查这是否与您真正想要的相符。

在这种情况下，作为您指定输入的一个简单示例，您的循环将第一个数字 (40) 与第二个数字 (50) 进行比较，将计数递减到 -1 （这根本没有意义），然后执行实际上不可能的 if检查（计数为 -1 或 +1，绝不为 0），然后进一步进入“我什至不知道你想在这里做什么”。

因此，忽略你所写的灵感，因为它没有意义，这里有一个在 O(n) 中完成它的通用方法，但需要注意的是，输入范围需要非常小才能使该算法工作：

int MAX_INPUT_VALUE = 1000;
int[] counts = new int[MAX_INPUT_VALUE];
int max = 0;
int answer = 0;
for (int input : inputs) {
  int newCount = ++counts[input];
  if (newCount > max) {
    answer = input;
    max = newCount;
  }
}

理论上，这是

O(max(n, m))

，其中

n

是输入中的元素数量，m 是输入中的最大数字（并且只是因为在 java 中，数组在创建时用零填充，是一个

O(m)

操作）。

摆脱对有限输出范围的烦人依赖的一个简单方法是使用 HashSet。但是，听起来你不被允许这样做。