这个问题之前有人问过。但是我只想知道我的代码有什么问题。它在 lintcode 上通过了大部分测试用例,但并非全部。
给定一个整数数组,多数数是出现次数超过数组大小一半的数。找到它。
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
Collections.sort(nums);
int j = 0, count = 0, out = 0, size = nums.size();
for(int i = 0; i < size; i++) {
if(nums.get(j) == nums.get(i)) {
count++;
if(count > size/2){
out = nums.get(i);
}
} else {
count = 1;
j = i;
}
}
return out;
}
}
编辑
我按照答案的建议将代码更改为 j = i & count = 1。
例如对于输入 [1,1,1,2,2,2,2] 输出应该是 2。 我的代码在这种情况下有效。它不适用于大输入情况。
我不想要其他解决方案,因为我已经在其他站点上找到了许多 O(n) 解决方案。我只想修复我自己的代码并知道我做错了什么。
最佳答案
有一个智能解决方案可以在 O(n) 最坏情况下运行,并且没有额外的空间:
public static int majorityNumber(List<Integer> nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0)
candidate = num;
if (num == candidate)
count++;
else
count--;
}
return candidate;
}
请注意,它假定存在多数值,否则返回任意值。
关于java - 查找数组中的多数数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33749942/