LintCode：Majority Number / Majority Number II / Majority Number III

矫情吗；* 2022-07-31 01:52 180阅读 0赞

今天看到LintCode一题：

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.  
Find it.

example:Given \[1, 2, 1, 2, 1, 3, 3\], return 1.

给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。

例子：给出数组\[1,2,1,2,1,3,3\] 返回 1。

我的做法是使用hashmap将数组中的数与键对应，统计个数与值对应。

public class Solution {
        /**
         * @param nums: A list of integers
         * @return: The majority number that occurs more than 1/3
         */
        public int majorityNumber(ArrayList<Integer> nums) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (Integer integer : nums) {
    			if (map.get(integer) != null) {
    				map.put(integer, map.get(integer)+1);
    			}else {
    				map.put(integer, 1);
    			}
    		}
    		for (Integer integer : map.keySet()) {
    			if (map.get(integer) > nums.size()/3) {
    				return integer;
    			}
    		}
    		return 0;
        }
    }

以上做法对Majority Number / Majority Number II / Majority Number III 这三道题来说都可以用。

我在网上找到一个解决方法如下的：

思路：三三抵销，同时记录剩下的值各自出现的次数，出现次数多的值为答案。

我也将其测试了一下，发现不通过。代码如下：

public int majorityNumber(ArrayList<Integer> nums) {
    		int count1 = 0, count2 = 0;
    		int flag1 = 0, flag2 = 0;
    		int temp = 0;
    		for (int i = 0; i < nums.size(); i++) {
    			temp = nums.get(i);
    			if (count1 == 0) {
    				flag1 = temp;
    			}
    			if (count2 == 0 && temp != flag1) {
    				flag2 = temp;
    			}
    			if (temp != flag1 && temp != flag2 && count1 != 0 && count2 != 0) {
    				count1--;
    				count2--;
    			}
    			if (temp == flag1) {
    				count1++;
    			}
    			if (temp == flag2) {
    				count2++;
    			}
    		}
    		return count1 > count2 ? flag1 : flag2;
    	}

不能通过后，我看了一下，是抵消会出问题。会存在这样一种情况，假如有3\*n+1个数，当恰好前面的3\*n个抵消了，多出来的1个就会被当做主元素，其实第3\*n+1个不一定是主元素。（3\*n+2个数也是这样）

举例说明：

\[1,2,3,4\]这时count1=1，count2=,0，所以返回4。

\[1,2,3,4,5\]这个时候count1=count2=1，所以返回5。

在这两种情况下都是没解的。

不知道是我认识不够，还是什么原因。我在网上看了几篇文章，用这种方法，竟然通过测试了。小伙伴们看到这里的话，如果知道怎么解释或者解决这个问题的话，麻烦给我解释一下。谢谢了！