# 169.Majority Element

169.Majority Element

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

You may assume that the array is non-empty and the majority element always exist in the array.

class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};


/*solution1 O(n^2) 20ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
/*遇到有重复元素的，我们仅以最后一个元素做参照，来对该元素出现次数进行统计*/
while(nums[i]==nums[i+1])
i++;
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};


1.sort

/*solution2 sort 40ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};



2.hash-table

hash-table的思路比较直接，维护一个unodered-map ,每次在hash-table里搜索nums[i]，搜索到则让以nums[i]为键值的元素加1即可，见代码:

/*solution4 use hash-table time-complexity O(n) memory-complexity O(n)*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
unordered_map<int,int> num_count;
int i=0,size=nums.size();
for(i=0;i<size;i++){
if(num_count.find(nums[i])==num_count.end())
num_count[nums[i]]=0;
else
num_count[nums[i]]++;
if(num_count[nums[i]]>=size/2)
return nums[i];
}
return -1;
}
};



3.majority voting algorithm

The algorithm is carried out in two steps:

Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: if the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate. Determine if the remaining element is a valid majority element. With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence’s length. If so, the candidate is the majority. Otherwise, the sequence doesn’t contain a majority.

1. 不断删除数组中的元素直到仅剩下一个
2. 判断剩下的那一个是否真的是majority

class Solution {
public:
int majorityElement(vector<int>& nums) {
int curIndex=0,count=0,i=0;
for(i=0;i<nums.size();i++){
nums[curIndex]==nums[i]?count++:count--;
if(!count){
curIndex=i;
count=1;
}
}
return nums[curIndex];
}
};



# 一.你能准确写出二分查找吗？

————==写出这篇博文献给和我一样对二分查找的思路毫无头绪但又不甘于死记硬背的人们==。

# 二.利用循环不变式来证明边界取值的正确性

note:

1. 本文中，文字说明部分的’=’究竟是赋值还是逻辑判断请根据上下文推断。
2. 算法推导过程中的mid的计算采用(low+high)/2的方式，因为只是推导，所以无需考虑溢出的问题，但是代码中全部采用low+(high-low)/2,推导过程中可认为两者值相等。
3. 在理论推导每次数组减少的长度时，mid是不能代换成left + (right - left)/2的。这种形式代表了非整型的运算，没有舍去小数部分，而在实际的运行过程中mid是会舍去小数部分的。

1. 初始化：它在循环的第一轮迭代开始之前，应该是正确的。
2. 保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。
3. 终止：循环能够终止，并且可以得到期望的结果。

1. 若Array[mid]< v,则v应该存在于[mid+1,high]区间内，舍弃区间[low,mid],数组减小长度为(mid-low+1),则数组每次至少减少1个单位,并且low应该指向mid+1的位置;
2. 若Array[mid]==v,则说明找到，返回mid;
3. 若Array[mid]>v,则v应该存在于[low,mid-1]区间内，舍弃区间[mid,high],数组减小长度为(high-mid+1),则数组每次至少减少1个单位,并且high指针应该指向mid-1位置;

class Solution {
public:
int binSearch(vector<int> &nums,int target) {
if(nums.empty())
return -1;
int low=0,high=n-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(nums[mid]<target)
low=mid+1;
else if(nums[mid]>target)
high=mid-1;
else
return mid;
}
return -1;
}
};


1. 若Array[mid]<v,则v应该存在于[mid+1,high]区间内，舍弃区间[low,mid],数组减小长度为(mid-low+1),则数组每次至少减少1个单位,并且low应该指向mid+1的位置;
2. 若Array[mid]== v,则最后一个v应该存在于[low,mid]区间内，舍弃区间[mid+1,high]，数组减小长度为(high-mid),当low==high时，减小长度为0，如不干预会进入死循环，high应该指向mid位置
3. 若Array[mid]>v,则v应该存在于[low,mid-1]区间内，舍弃区间[mid,high],数组减小长度为(high-mid+1),至少减少1个单位，且high应指向mid-1的位置

class Solution {
public:
vector<int> searchLow_bound(vector<int>& nums, int target) {
vector<int> res(2,-1);
if(nums.empty())
return res;
int low=0,size=nums.size(),high=nums.size()-1,mid=0;
while(low<high){
mid=low+(high-low)/2;
if(nums[mid]>target)
high=mid-1;
else if(nums[mid]==target)
high=mid;
else
low=mid+1;
}
if(nums[low]==target)
res[0]=low;
}
};


class Solution {
public:
vector<int> searchLast(vector<int>& nums, int target) {
vector<int> res(2,-1);
if(nums.empty())
return res;
int low=0,size=nums.size(),high=nums.size()-1,mid=0;
while(low+1<high){
mid=low+(high-low)/2;
if(nums[mid]<target)
low=mid+1;
else if(nums[mid]==target)
low=mid;
else
high=mid-1;
}
if(nums[low+1]==target&&size>1)
res[1]=low+1;
else if(nums[low]==target)
res[1]=low;
else
res[1]=-1;
return res;
}
};


# 三.总结：如何写出正确的二分查找代码？

(1)大体框架必然是二分，那么循环的key与array[mid]的比较必不可少，这是基本框架;

(2)循环的条件可以先写一个粗略的，比如原始的while(left<=right)就行，这个循环条件在后面可能需要修改；

(3)确定每次二分的过程，要保证所求的元素必然不在被排除的元素中，换句话说，所求的元素要么在保留的其余元素中，要么可能从一开始就不存在于原始的元素中；

(4)检查每次排除是否会导致保留的候选元素个数的减少？如果没有，分析这个边界条件，如果它能导致循环的结束，那么没有问题；否则，就会陷入死循环。为了避免死循环，需要修改循环条件，使这些情况能够终结。新的循环条件可能有多种选择：while(left< right)、while(left< right-1)等等，这些循环条件的变种同时意味着循环终止时候选数组的形态。

(5)结合新的循环条件，分析终止时的候选元素的形态，并对分析要查找的下标是否它们之中、同时是如何表示的。

对于(3)，有一些二分算法实现不是这样的，它会使left或right在最后一次循环时越界，相应的left或right是查找的目标的最终候选，这一点在理解时需要注意。当然，不利用这个思路也可以写出能完成功能的二分查找，而且易于理解。

1.查找排序数组中某个数出现的次数。

# 三.如何使用位操作

## 1.and操作

and操作可以用来取某一位二进制数，例如二进制数:0110,在与1进行and操作后，就可以取出其最后一位0 and操作可以用于判断奇数偶数，因为二进制数末尾为1时，为奇数;末位为0时，为偶数。

## 2.or操作

or操作可以对二进制数某一位赋值，比如要将某二进制数最后一位赋值为1，只需将其与1进行or操作，那么如何赋值为0呢?很简单，与1进行or之后减1即可。 这个操作可以用来寻找与一个数最相近的偶数

## 3.xor操作

xor操作即异或，常用于对某一位进行取反，因为异或操作可以被解释为"是不是相同，相同得0，不同得1" xor的逆运算是它本身，也就是说如果有a,b两个数，(a^b)^b=a,一个数与另一个数进行连续的两次xor操作得到的是它本身，根据这个性质可以进行加密运算，比如 > 我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。 这个例子引用自网络上一篇博文:http://www.matrix67.com/blog/archives/263 接着我们看看xor的另一个用途，用于交换两个int值 在我们之前使用的交换操作中，都需要一个临时变量，那么能不能在不用临时变量的情况下完成交换呢？当然可以。 假如有a，b两个int值，a=1，b=2，对a，b进行下面的运算  a=a^b b=a^b a=a^b  看起来很诡异，其实这个操作的确能起到swap的作用，第一次赋值后a==a^b,第二次操作b被赋值为(a^b)^b,也就是a,第三次操作a赋值为a^(a^b),也就是b，到这里就完成了这个交换的过程而且没有使用临时变量。

## 5.shl操作

a shl b也就是将二进制数每位左移b位，也就是在后面加b个0，实际效果相当于乘以2的b次幂，比如100 shl 2==400。 通常认为a shl 1比a*2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 – 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。

## 6.shr操作

a shr b也就是将二进制数每位右移b位，也就是去掉后b位,效果相当于除以2的b次幂 下面列举的是位操作常见应用，引用自http://www.matrix67.com/blog/archives/263 功能 | 示例 ---|--- 去掉最后一位 | (101101->10110) x shr 1 在最后加一个0 | (101101->1011010) x shl 1 在最后加一个1 | (101101->1011011) x shl 1+1 把最后一位变成1 | (101100->101101) x or 1 把最后一位变成0 | (101101->101100) x or 1-1 最后一位取反 | (101101->101100) x xor 1 把右数第k位变成1 | (101001->101101,k=3) x or (1 shl (k-1)) 把右数第k位变成0 | (101101->101001,k=3) x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) x xor (1 shl (k-1)) 取末三位 | (1101101->101) x and 7 取末k位 | (1101101->1101,k=5) x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) x and (x+1) 把右起第一个0变成1 | (100101111->100111111) x or (x+1) 把右边连续的0变成1 | (11011000->11011111) x or (x-1) 取右边连续的1 | (100101111->1111) (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) x and (x xor (x-1))

# 75. Sort Colors

75.Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Follow up: A rather straight forward solution is a two-pass algorithm using counting sort.

First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

/*solution1 4ms use counting sort*/
class Solution {
public:
void sortColors(vector<int>& nums) {
int i=0,j=0,k=0;
vector<int> zero;
vector<int> one;
vector<int> two;
for(i=0;i<nums.size();i++){
switch(nums[i]){
case 0:
zero.push_back(nums[i]);
break;
case 1:
one.push_back(nums[i]);
break;
case 2:
two.push_back(nums[i]);
break;
}
}
for(i=0;i<zero.size();i++)
nums[i]=zero[i];
for(i,j=0;j<one.size();i++,j++)
nums[i]=one[j];
for(i,k=0;k<two.size();i++,k++)
nums[i]=two[k];
}
};


1. nums[cur]==0 应该将其与low指向的元素交换，因为nums[low]始终 ==1或low ==cur,所以交换后的nums[cur]已经到位,只需cur++，low++
2. nums[cur]==1 已经就位，cur++即可
3. nums[cur]==2 应该将其与high指向的元素作交换，但是high指向的元素的值不确定，所以只能让high–，cur不变

1 0 2 2 1 0
^         ^
L         H
M

Mid != 0 || 2
Mid++

1 0 2 2 1 0
^ ^       ^
L M       H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 1 2 2 1 0
^ ^     ^
L M     H

Mid == 2
Swap High and Mid
High--

0 1 0 2 1 2
^ ^   ^
L M   H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 0 1 2 1 2
^ ^ ^
L M H

Mid == 2
Swap High and Mid
High--

0 0 1 1 2 2
^ ^
L M
H



class Solution {
public:
void sortColors(vector<int>& nums) {
int low=0,high=nums.size()-1,cur=0;
while(cur<=high){
if(nums[cur]==0)
swap(nums[cur++],nums[low++]);
else if(nums[cur]==1)
cur++;
else if(nums[cur]==2)
swap(nums[cur],nums[high--]);
}
}
};


# 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

1 2 3
4 5 6
7 8 9


7 8 9
4 5 6
1 2 3


7 4 1
8 5 2
9 6 3


class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int i=0,j=0,row=matrix.size(),col=matrix[0].size(),tmp=0;
int low=0,high=matrix.size()-1;
while(low<high)
swap(matrix[low++],matrix[high--]);
for(i=0;i<row;i++){
for(j=i+1;j<col;j++)
swap(matrix[i][j],matrix[j][i]);
}
}
};