算法：查找多数元素

题目

找出一个数组中占50%以上的元素，即寻找多数元素，并且多数元素是一定存在的假设。

分析

对数组的操作，一般会要求时间复杂度和空间复杂度。所以，最常用的方法就是设置两个指针，分别指向不同的位置，不断调整指针指向来实现O（N）时间复杂度内实现算法。常见的面试题有：拼接一个最大/小的数字、合并两个有序数组、调整数组顺序使奇数位于偶数前面、查找多数元素、数组中的重复元素。

思路1：将数组排序，则中间的那个元素一定是多数元素，该代码的时间复杂度为O（NlogN）。

思路2：利用HashMap来记录每个元素的出现次数，该代码的时间复杂度为O（N），空间复杂度为O（N）。

思路3：Moore’s voting algorithm。这个算法是解决这样一个问题：从一个数组中找出出现半数以上的元素。他的基本思想是：每次都找出一对不同的元素，从数组中删掉，直到数组为空或只有一种元素。 不难证明，如果存在元素e出现频率超过半数，那么数组中最后剩下的就只有e。该算法的时间复杂度为O(n)，空间复杂度为O(1)。不需要额外的空间来保存原始数组。

具体算法是：在遍历数组的过程中，保存两个值，一个是数组中数字，一个是出现次数。当遍历到下一个数字时，如果这个数字跟之前保存的数字相同，则次数加1，如果不同，则次数减1。如果次数为0，则保存下一个数字并把次数设置为1，由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

思路4：Bit Manipulation，很机智的一种方法。从位的角度去理解，一个元素在数组中出现半数以上造成的影响。

JAVA实现

public class MajorityElement {
	/**
	 * 思路1：将数组排序，则中间的那个元素一定是多数元素
	 * 该代码的时间复杂度为O（NlogN）
	 * 
	 * @param nums 整形数组
	 * @return
	 */
	public static int search1(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length/2];
	}
	
	/**
	 * 思路2：利用HashMap来记录每个元素的出现次数
	 * 该代码的时间复杂度为O（N），空间复杂度为O（N）
	 * 
	 * @param nums
	 * @return
	 */
	public static int search2(int[] nums) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i=0; i<nums.length; i++) {
			int key = nums[i];
			if (map.containsKey(key)) {
				int sum = map.get(key);
				map.put(key, ++sum);
			} else {
				map.put(key, 1);
			}
		}
		
		int n = nums.length/2;
		Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
		Iterator<Map.Entry<Integer, Integer>> iterator = entrySet.iterator();
		while (iterator.hasNext()) {
			Map.Entry<Integer, Integer> entry = iterator.next();
			if (entry.getValue() > n) {
				return entry.getKey();
			}
		}
		return 0;
	}
	
	/**
	 * Moore’s voting algorithm
	 * 这个算法是解决这样一个问题：从一个数组中找出出现半数以上的元素。
	 * 他的基本思想是：每次都找出一对不同的元素，从数组中删掉，直到数组为空或只有一种元素。 
	 * 不难证明，如果存在元素e出现频率超过半数，那么数组中最后剩下的就只有e。
	 * 该算法的时间复杂度为O(n)，空间复杂度为O(1)。不需要额外的空间来保存原始数组.
	 * @param nums
	 * @return
	 */
	public static int search3(int[] nums) {
		int majorityIndex = 0;
		int count = 1;
		int len = nums.length;
		for(int i = 1; i < len; i++) {
			if (nums[majorityIndex] == nums[i]) {
				++count;
			} else {
				--count;
			}
			if (count == 0) {
				majorityIndex = i;
				count = 1;
			}
//			if (count == 0 && i < len-1) {
//				majorityIndex = ++i;
//				count = 1;
//			}
//			if(majorityIndex>nums.length-1) {
//				majorityIndex=nums.length-1;
//			}
		}
		return nums[majorityIndex];
	}
	
	/**
	 * Moore’s voting algorithm
	 * 这个算法是解决这样一个问题：从一个数组中找出出现半数以上的元素。
	 * 他的基本思想是：每次都找出一对不同的元素，从数组中删掉，直到数组为空或只有一种元素。 
	 * 不难证明，如果存在元素e出现频率超过半数，那么数组中最后剩下的就只有e。
	 * 该算法的时间复杂度为O(n)，空间复杂度为O(1)。不需要额外的空间来保存原始数组.
	 * @param nums
	 * @return
	 */
	public static int search4(int[] nums) {
		int searchNum = nums[0];
		int count = 0;
		for (int num: nums) {
			if (count == 0) {
				searchNum = num;
				count++;
			} else if(searchNum == num) {
				count++;
			} else {
				count--;
			}
		}
		return searchNum;
	}
	
	/**
	 * Bit Manipulation，很机智的一种方法。从位的角度去理解，一个元素在数组中出现半数以上造成的影响。
	 * 
	 * @param nums
	 * @return
	 */
	public static int search5(int[] nums) {
	    int len = 32, size = nums.length;
	    int count = 0, mask = 1, ret = 0;
	    for(int i = 0; i < len; ++i) {
	        count = 0;
	        for(int j = 0; j < size; ++j)
	            if((mask & nums[j])!=0) count++;
	        if(count > size/2) ret |= mask;
	        mask <<= 1;
	    }
	    return ret;
	}

	
	public static void main(String[] args) {
		// 出现次数超过总数量的一半
		int[] nums = {1,2,2,2,2,2,2,3,3,3,3,2,3};
		System.out.println("search1=="+search1(nums));
		System.out.println("search2=="+search2(nums));
		System.out.println("search3=="+search3(nums));
		System.out.println("search4=="+search4(nums));
		System.out.println("search5=="+search5(nums));
	}
}