分治算法18题

1. 求众数 (169) 简单

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

题解：

1）对数组排序，由于众数大于n/2，则n/2+1处一定是该众数。又由于索引从0开始，即索引n/2为众数。

算法时间复杂度O（nlogn）

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int sz = nums.size()/2+1;
 5         sort(nums.begin(),nums.end());
 6         
 7         return nums[sz-1];
 8         //cout<<nums[sz]<<endl;
 9     }
10 };

View Code

2）摩尔投票法 Moore Voting

O(n) 的时间和 O(1) 的空间

这种投票法先将第一个数字假设为过半数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将下一个值设为候选过半数。以此类推直到遍历完整个数组，当前候选过半数即为该数组的过半数。

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         //不用判断数组为空
 5         int res = nums[0];
 6         int count = 1;
 7         int sz = nums.size();
 8         for(int i=1;i<sz;i++){
 9             if(count==0){
10                 res = nums[i];
11                 count = 1;  //要重新赋值1
12             }else if(res == nums[i]){  //count!=0;nums[i]==res;
13                 count++;
14             }else{
15                 count--;
16             }
17             
18         }
19         return res;
20     }
21 };

View Code

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int res = 0, cnt = 0;
 5         for (int num : nums) {
 6             if (cnt == 0) {res = num; ++cnt;}
 7             else (num == res) ? ++cnt : --cnt;
 8         }
 9         return res;
10     }
11 };

View Code

3）位操作 Bit Manipulation

将中位数按位来建立，从0到31位，每次统计下数组中该位上0和1的个数，如果1多，那么我们将结果res中该位变为1，最后累加出来的res就是过半数了

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int res=0, n = nums.size();   
 5         
 6         for(int i=0;i<32;i++){
 7             int ones = 0, zeros = 0;
 8             
 9             for(int num : nums){
10                 if(ones > n/2 || zeros > n/2)
11                     break;
12                 if(num & (1<<i)) //第i位是1
13                     ones++;
14                 else
15                     zeros++;
16             }
17             
18             if(ones>zeros){
19                 res = (res | (1<<i));
20             }
21         }
22         return res;
23     }
24 };

View Code

2. 数组中的第K个最大元素（215）中等

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

题解：　　