这个问题以前有人问过但是我只想知道我的代码有什么问题。它在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/

10-11 13:53