一个题：给定N个数，求出现次数大于N/2的数字，要求时间复杂度为O(N)，空间复杂度为O(1)。

如果不要求时间复杂度和空间复杂度，有多种解法吧：1. 排序：如果这个数字存在，那么排序后它一定在N/2这个位置上。可以先排序，再验证N/2这个位置上的数字满不满足条件。

1. 用HashMap

但是有这些限制就不行了，可以使用摩尔投票法：在每一轮投票过程中，从数组中找到一对不同的元素，将其从数组中删除。这样不断删除直到无法进行删除。如果数组空了，那么不存在 这样的元素。如果还剩一种数字，那么这个数字可能是结果。

代码如下：

public int majorityElement(int[] nums) {
	
	
	int majority = -1;
	int count = 0;
	
	
	for (int num : nums) {
	
		if (count == 0) {
			majority = num;
			count++;
		}
		else {
			if (majority == num)
				count++;
			else
				count--;
		}
		
	}
	
	
	if (count <= 0)
		return -1;
		
	for (int num : nums) {
		if (num == majority)
			count++;
	}
	
	
	if (count > nums.length / 2)
		return majority;
	
	return -1

}

这道题还可以有拓展：给定N个数，求出次数大于N/3的数字，要求时间复杂度为O(N)，空间复杂度为O(1). 这道题和上一题是同样的思路，即摩尔投票法。这种元素的个数可能为0，1，2。同样是分两步：1. 找到两个候选元素

1. 验证这两个元素是不是满足条件。 代码如下：

··· public List majorityElement(int[] nums) { //moore voting //0632 int candidate1 = 0, candidate2 = 0, times1 = 0, times2 = 0; int n = nums.length; for(int i = 0; i < n; i++){ if(nums[i] == candidate1) { times1++; } else if(nums[i] == candidate2){ times2++; } else if(times1 == 0) { candidate1 = nums[i]; times1 = 1; } else if(times2 == 0){ candidate2 = nums[i]; times2 = 1; } else{ times1--;times2--; } }

    times1 = 0; times2 = 0;  
    for(int i = 0; i < n; i++){  
        if(nums[i] == candidate1) times1++;  
        else if(nums[i] == candidate2) times2++;  
    }  
      
    List<Integer> res = new ArrayList<Integer>();  
    if(times1 > n/3) {  
        res.add(candidate1);  
    }  
    if(times2 > n/3) {  
        res.add(candidate2);  
    }  
    return res;  
    //0649  
}   ···