leetcode解题笔记：Majority Element I & II

剑指offer第29题，leetcode 169,229 题目：找到数组中出现次数超过一半的数字

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

解法一

由于要寻找的数字在数组中出现次数超过一半，这就说明如果整个数组排好序，那么中间的那个数肯定就是我们的答案。 因此可以考虑借鉴快排的方法，我们先随机选择一个数字，把比它小的都放它左边，比它大的都放它右边，这样就找到了这个数字最终的位置。

如果这个位置正好是数组中间位置，那么这个数就是我们要的答案。如果这个位置在数组中间位置的右边，说明我们要找的数在这个数的左边，因此可以继续在其左边的数组中查找数组中间的那个数如果这个位置在数组中间位置的左边，说明我们要找的数在这个数的右边，因此可以继续在其右边的数组中查找数组中间的那个数 public class Solution { public int majorityElement(int[] nums) { int start=0; int end = nums.length-1; //利用快排思想找到中位数 int index = partition(nums,start,end); while(index != nums.length/2){ if(index > nums.length/2){ end = index-1; index = partition(nums,start,end); }else{ start = index+1; index = partition(nums,start,end); } } return nums[index]; } private int partition(int[] nums,int lo,int hi){ int i = lo-1; int j = hi+1; while(true){ while(nums[++i]<=nums[lo]){ if(i == hi) break; } while(nums[lo]<=nums[--j]){ if(lo == j) break; } //此时从左开始找到了第一个比基准数nums[lo]大的数 //从右开始找到了一个比基准数nums[lo]小的数 //如果i在j的左边，则此时需要交换这两个数 if(i>=j) break; int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } //此时代表i与j相等或i大于j，此时j左边的都比基准数小，i右边的都比基准数大 int tmp = nums[lo]; nums[lo] = nums[j]; nums[j] = tmp; return j; } }

很可惜的是这种方法在leetcode里一直超时…………

解法二

从另一个角度来想问题，数组中有一个数字出现的次数超过数组长度的一半，这说明它出现的次数比余下所有数出现次数的和还多。 因此我们可以考虑在遍历数组时保存两个值，一个是数组中的一个数字，一个是这个数字出现的次数。 当我们遍历到下一个数字的时候：

如果下一个数字和我们保存的相同，次数加1如果下一个数字和我们保存的不同，次数减1如果次数等于0了，说明保存的数和已经遍历过的其他数抵消了，那我们另下一个数字为要保存的数字。

最后剩下了次数没被抵消的数就是我们要找的数。

public class Solution { public int majorityElement(int[] nums) { int count = 1; int index = nums[0]; for(int i = 1; i<nums.length; i++){ if(count == 0){ index = nums[i]; count = 1; }else if(nums[i] == index){ count++; }else{ count--; } } return index; } }

以上两种方法都是O(n)的时间复杂度。

follow-up

Majority Element II 中，题目改成了找出现次数超过1/3的数字

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

这时，解法一明显已经不适用了，只能走解法二的思想。

题目给的hint是 How many majority elements could it possibly have? 对于出现次数超过1/3的数，最多可以有2个，因此我们设定两个候选数。

记变量candidate1, candidate2为候选众数； count1, count2为它们对应的出现次数

遍历数组，记当前数字为num[i]

若num[i]与candidate1或candidate2相同，则将其对应的出现次数加1

否则，若count1或count2为0，则将其置为1，对应的候选众数置为num[i]

否则，将count1与count2分别减1

最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。

public class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<Integer>(); if(nums.length == 0){ return result; } //根据hint，最多有两个出现次数超过1/3的数 //因此，统计两个候选数 int count1 = 0; int count2 = 0; int candidate1 = nums[0]; int candidate2 = nums[0]; for(int i = 0; i<nums.length; i++){ if(nums[i] == candidate1){ count1++; }else if(nums[i] == candidate2){ count2++; }else if(count1 == 0){ candidate1 = nums[i]; count1 = 1; }else if(count2 == 0){ candidate2 = nums[i]; count2 = 1; }else{ count1--; count2--; } } count1 = 0; count2 = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == candidate1) count1++; else if (nums[i] == candidate2) count2++; } if (count1 > nums.length / 3) result.add(candidate1); if (count2 > nums.length / 3) result.add(candidate2); return result; } }