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.

这道题要求寻找数组中的多数元素,也就是出现次数超过数组长度一半的元素,最容易想到的方式就是用两个指针对其进行扫描,再用一个count变量进行计数,遇到count超过数组长度一半的情况就返回,思路非常简单,代码如下:

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;
    }
};

这样一个简单的操作,让一个TLE的算法击败了百分之五十以上的提交,运行时间为20ms。

之后又思考了别的方法,主要是以下三种:

1.sort

既然是majority,在经过排序后,如果比较小,从第一个元素开始,那么最后一个majority必然位于中间位置;如果比较大,导致最后一个元素也为majority,那么中间位置也依然是majority;综上所述,在两种极端情况下,都可以保证中间是majority,那么在其他情况下一定可以保证最中间的元素是majority。

既然如此,代码也就十分容易写出了;

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

时间复杂度为O(nlog n),速度并不是很快,那么有没有办法将时间复杂度降到O(n)呢?

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;
    }
};

时间复杂度O(n),空间复杂度O(n),但leetcode给出的运行时间为48ms,看来还需要再优化

3.majority voting algorithm

这个算法专门用来解决数组中多数元素的问题,只需要one-pass就可以解决问题

先来看看这个算法的描述:

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

关于这个算法的演示,请见:http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html#step13

下面贴出代码:

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];
    }
};

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

先看看定义

二分查找的搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则查找成功;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

思路很简单以至于大多数人都能讲出来,但是有多少人能一次写出bug-free的代码?《编程之美》第2.16节的最长递增子序列算法,如果想实现O(n2)到O(nlogn)的时间复杂度下降,必须借助于二分算法的变形。其实很多算法都是这样,如果出现了在有序序列中元素的查找,使用二分查找总能提升原先使用线性查找的算法的性能。

很多人觉得二分算法简单,但随手一写会发现诸如死循环,边界条件无法确定的问题,提供充足的时间,仅有约10%的专业程序员能够完成一个正确的二分查找,看来,二分查找并不是我们想象的那么简单。网络上的资料大多对边界值的确定避而不谈,即使进行讲解,思路也有些凌乱并且不适合我这种初学者,在参考多篇文章之后,我对二分算法有了一个新的认识。

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

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

note:

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

循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法,它是一个需要保证正确断言。对于循环不变式,必须证明它的三个性质:

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

例1:找出数组中值为v的元素,不存在时返回-1

初始化:初始区间为[0,n-1],low初始值为0,high初始值为n-1,若v存在于数组中,则其必然存在于区间[low,high中],正确。

保持:

  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位置;

终止:

根据上面的讨论,我们明确了每个if判断之后high,low指针的移动情况,但是我们还需要确定循环条件,我们看到,无论是情况1还是情况3,数组每次至少减少1个单位,考虑当low==high时,可以推出low或high==mid,但是我们的数组减小长度要么为(mid-low+1),要么为(high-mid+1),不管什么情况总是保证每次减少1,所以不会出现死循环的情况。

根据上面的分析,我们确定循环条件为:low<=high

代码如下:

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;
    }
};

例2: 二分查找返回key(可能有重复)第一次出现的下标x,如果不存在返回-1

初始化:初始区间为[0,n-1],low初始值为0,high初始值为n-1,若v存在于数组中,则其必然存在于区间[low,high],正确。

保持:

  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的位置

终止: 通过上面的讨论,我们知道low==high时应该进行干预,并且应该在循环结束后检查Array[low]是否等于target,如果相等则说明找到了某个数第一次出现时的位序。

综上所述,循环条件为:low< high

代码如下:

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;
    }
};

例3.二分查找返回key(可能有重复)最后一次出现的下标x,如果不存在返回-1

初始化:

初始区间为[0,n-1],low初始值为0,high初始值为n-1,若v存在于数组中,则其必然存在于区间[low,high],正确。

保持:

若Array[mid]< v,则v存在于区间[mid+1,high],舍弃区间[low,mid],区间减少的长度为(mid-low+1),至少为1,同时令low指向mid+1。

若Array[mid]==v,则v存在于区间[mid,high],舍弃区间[low,mid-1],区间减小长度为(mid-low),同时令low指向mid,根据前面的分析,我们知道这种情况下如果low==high就会出现死循环,同时,如果high==low+1也会导致死循环,因为mid=(low+high)/2。

若Array[mid]>v,则v存在于区间[low,mid-1],舍弃区间[mid,high],区间减小长度为(high-mid+1),至少为1,同时令high指向mid-1的位置。

终止: 根据上面的讨论,我们知道low必须小于high,且low+1也要小于high。

故循环条件为low+1< high

另外由于是寻找最后一次出现的下标,所以循环结束后还需要检查Array[low+1]是否等于target,不相等则检查Array[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就是出现次数,时间复杂度O(logn).

一.什么是位操作

整数在计算机内是以二进制数的形式存储的,所谓的位操作,就是直接对内存中的组成整数的二进制数进行操作。 最基本的位操作有 “与” “或” “异或” “取反” “左移” “右移” 六种

二.基础的位操作

操作 | 运算规则 ---|--- 与 & | 两数同为1时结果为1 或 \| | 两数同为0时结果为0 异或 ^| 两数相同结果为0,不同为1 取反 ~| 0得1 1得0 左移 << |二进制数各位向左移若干位,高位丢弃,低位补0 右移 >> |各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

三.如何使用位操作

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,到这里就完成了这个交换的过程而且没有使用临时变量。

4.not运算

not也就是非运算,将二进制数每一位全部取反,使用not运算时要格外小心,你需要注意整数类型有没有符号。如果not的对象是无符号整数(不能表示负数),那么得到的值就是它与该类型上界的差,因为无符号类型的数是用$0000到$FFFF依次表示的。

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

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];
    }
};

不过这个解法并不能算作完美的算法,因为申请了额外的空间,并且进行了多次的遍历。

现在考虑能不能用恒定的空间和one-pass来解决问题,考虑到只有三种元素,0 1 2,那么我们可以借鉴快排的思路,以1为pivot,然后把0放在1左边,2在1右边,这是大致的思路。

要实现这个算法,我们需要三个指针,low high和cur,其中low,high分别指向0和2组成的序列的边界,cur从最左端开始向后遍历,那么有以下几种情况:

  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

由此可见,循环条件应该是mid<=high

代码如下:

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?

要将image旋转90度,其实就是将矩阵旋转90度,以下面这个矩阵为例:

1 2 3
4 5 6
7 8 9

想要将其顺时针旋转90度,可以先以中间行为轴,上下对应行进行交换,对于这个例子,矩阵在经过这样的变化后,变成:

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]);
        }
    }
};

时间复杂度为O(n),空间复杂度为O(1),符合题目中要求的constant-place