### 169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
这题可太有意思了，意思就是找到众数，并且这个众数的个数是大于n/2的。方法很多，比如（1）哈希表，记录每个元素出现的次数，边记录边判断是否个数>n/2。（2）随机数，随机一个数，判断它的次数是否大于n/2。但是这两种方法属于是正常做法，作为不正常的我们自然要另辟蹊径。
这个数组其实存在这样一种性质，我们把数组中的元素分为两类，一类是众数，另一类是非众数。（1）我们删除一个众数和非众数，其实这个数组本身的性质仍然不变，即众数个数还是>n/2，说明这个操作没有影响。（2）我们删除两个不相等的非众数，数组性质还是不变，并且众数还比原来相对更多了，这是我们乐意看到的。那此时你就想问了，为什么不删除两个相等的数，因为我们的目的是通过两两相消不等的数，每次遇到相等的数就把它看作是众数，遇到不等的就两两相消，这样坐下来最后一定是留下的众数，因为众数的个数永远是最多的（参考刚刚说的两个性质）。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 1, candidate = nums[0];
for(int i = 1;i < nums.size();i ++ ){
if(nums[i] != candidate){
cnt --;
if(cnt < 0){
cnt = 1;
candidate = nums[i];
}
}
else{
cnt ++;
}
}
return candidate;
}
};
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
第一种方法，直接开辟一个新的数组，每个元素向右移动k个位置，使用(i + k) % n实现，如下所示：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> temp(n);
for(int i = 0;i < n;i ++ ){
temp[(i + k) % n] = nums[i];
}
nums = temp;
}
};
不过题目要求用O(1)的原地算法实现，也就是不能重新开辟数组。可以发现一个规律，最终的数组就是原数组的后k % n个元素移到前面，前n - k % n个元素移到后面，所以直接翻转原数组，然后分别对前后两端再翻转，如下所示：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};