LeetCode-Majority Element

超、凢脫俗 2022-08-06 13:11 290阅读 0赞

题目：

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

先给出最容易想的办法，比较渣。。

public int majorityElement(int[] num) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < num.length; i++) {
            	Integer times = map.get(new Integer(num[i]));
            	if (times == null) {
            		times = 0;
            	} 
            	map.put(new Integer(num[i]), ++times);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            	if (entry.getValue() > num.length/2) {
            		return entry.getKey();
            	}
            }
            return 0;
        }

看看这个更简练的办法，竟然运行速度比上面那个高效，好吧！上代码

public int majorityElement(int[] num) {
           Arrays.sort(num);
           return num[num.length / 2];
        }

是不是更加的简练，具体为啥就不解释了。看一个位操作，开拓下解题思路，如下方法也许不是最高效的。具体方法为，迭代一个整型的每个为，故外层循环是32次。在内层循环统计数组num中的数在第i位是为0的多还是1的多，因为majority出现次数多余n/2次，所以出现次数多的1或者0就是这个数在第i位的位。以此来构造一个majority数。其实这个也算是暴力破解，嵌套循环，但是这里的技巧就是外层是按位循环。。。

public int majorityElement(int[] num) {
    		int ret = 0;
    
    	    for (int i = 0; i < 32; i++) {
    	        int ones = 0, zeros = 0;
    	        for (int j = 0; j < num.length; j++) {
    	            if ((num[j] & (1L << i)) != 0) {
    	                ++ones;
    	            }
    	            else
    	                ++zeros;
    	        }
    	        if (ones > zeros) {
    	            ret |= (1L << i);
    	        }
    	    }
    	    return ret;
        }

还有一种思想，跟快速排序的分组有点相似，或者主要思想是一样的，可以拓展一下解题思路。。。

public int majorityElement(int[] num) {
    		int i = 0;
            int j = 1;
            while (j < num.length) {
                if (num[i] != num[j] ) {
                    swap(num, i+1, j);
                    i += 2;
                }
                ++j;
            }
            return num[i];
        }
    	public void swap(int[] A, int i, int j) {
    		int temp = A[i];
    		A[i] = A[j];
    		A[j] = temp;
    	}

最后一种思路，在《剑指offer》上看到的，是一种基于Boyer-Moore Algorithm，[http://goo.gl/64Nams][http_goo.gl_64Nams] ，讲的非常详细。上代码：

public int majorityElement(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int cnt = 0;
            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                if (cnt == 0) {
                    cnt++;
                    ret = nums[i];
                } else if (ret == nums[i]) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
            return ret;
         }

[http_goo.gl_64Nams]: http://goo.gl/64Nams