278.First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

版本序列已经sorted,又要求尽可能少调用API,所以最好的的办法就是Binary-Search,不过和常规的B-search相比,这里要做一些变化,当检测到mid版本有问题时,则说明应该去左半区继续查找;否则应该去右半区。最后返回low指针指向的版本号即可,代码如下:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int low=0,high=n-1,mid=0;
        while(low<=high){
            mid=low+(high-low)/2;
            if(isBadVersion(mid))
                high=mid-1;
            else
                low=mid+1;
        }
        return low;
    }
};

268.Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

要找出给定数组中缺少的元素,有两种思路:

  1. 等差数列求和
  2. 位操作中的异或操作
  3. 排序后二分查找

先说求和的思路,既然要找出序列0~n中存在而在给定数组中不存在元素,那就先对0~n的序列求和,求和之后再减去数组的所有元素和,差值就是missing number,代码如下:

/*solution1 32ms accumulate the sequence from 0 to n, 
not a good algorithm,when the test case is large,maybe overflow.
*/
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        return ((nums.size()*(nums.size()+1))>>1)-accumulate(nums.begin(),nums.end(),0);/*parameter 0 is initial value*/
    } 
};

这并不是一个好的思路,因为一旦数据量很大,size*(size+1)可能会溢出

下面说说位操作的思路,考虑六种位操作中只有异或操作能够用于这个问题的解答,所谓异或就是”相同则返回0,不同返回1”

根据异或的性质,如果一个序列中某一个数出现了一次而其他的数都出现了两次,那么容易证明所有元素进行异或之后剩下的那个就是只出现了一次的数,所以,我们大致思路如下:

  1. 让序列0~n中每一个元素先进行异或,得x
  2. 让数组中每一个元素进行异或,得y
  3. 返回x异或y的值

代码如下:

/*solution2 use bit manipulation and the property of XOR 36ms*/
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x=0,y=0,i=0;
        for(i=0;i<=nums.size();i++)
            x^=i;
        for(i=0;i<nums.size();i++)
            y^=nums[i];
        return x^y;
    } 
};

当然,我们发现之所以上面的算法要分成两轮循环来做,是因为两次循环条件不一样,正好相差一个值nums.size();正因为此,如果我们将x初始化为nums.size(),就可以one-pass解决问题,避免无用的循环。

优化后的代码如下:

/*solution3 one-pass,with bit manipulation 38ms*/
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x=nums.size(),y=0,i=0;
        for(i=0;i<nums.size();i++)
            x=x^i^nums[i];
        return x;
    } 
};

最后说说二分查找,首先要排序,这导致该算法最低时间复杂度也是O(nlogn),所以我们并不会采用这个方法;排序后进行二分查找,对中间元素的值和下标值进行比较,若中间值等于下标值,则说明missing number在右半区,否则在右半区。

240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

这道题是 Search a 2D Matrix系列中的第二题,由于不能保证每行第一个数比上一行最后一个数大,所以我们不能采用第一题的先确定行后确定列的思路。

不过遍历每行每列,以及遍历行之后在行内部进行二分的思路还是可以用的,但不够efficient

于是在参照讨论区之后,我采用了这样的算法:

从右上角开始,如果target大于右上角的值,因为右上角值是第一行最大值,最后一列最小值,所以target应该在之后的行中;若小于,则其毕存在于之前的列当中,代码如下:

/*solution1 264ms*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty())
            return false;
        int row=0,col=matrix[0].size()-1,size=matrix.size();
        while(row<size&&col>=0){
            if(matrix[row][col]==target)
                return true;
            else if(matrix[row][col]>target)
                col--;
            else if(matrix[row][col]<target)
                row++;
        }
        return false;
    }
};

运行时发现时间太长,觉得每次进入循环都要对是否相等进行判断,太过浪费时间,于是做出如下优化:

/*solution2 164ms*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int i = row-1,j =0;
        while(i>=0&&j<col){
            if(target>matrix[i][j])
                j++;
            else if(target<matrix[i][j])
                i--;
            else
                return true;
        }
        return false;
    }
};

238.Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

题目看起来很简单,但毕竟是一道medium的题,所以并不会像我们想的那么简单,我们首先粗略地考虑一般的情况:

  • 既然要算出某一元素以外其他元素的乘积,那么我们可以先算出所有元素的乘积,最后再除以不需要的元素即可

然而如果中间某个元素值为0呢?0做除数会引发异常,所以我们需要对Corner case进行讨论

  • 对于[0,1]这样的只有两个元素且其中一个元素的值为0的数组,我们发现只要交换一下两个元素然后返回即可。

修改之后,提交代码,发现自己对Corner case的讨论还不够完整,于是继续考虑。

  • 对于长度大于2的数组,又要再分两种情况:
    1. 长度大于2且只含有一个0,例如[9 0 3]这样的数组,我们发现只需要把0所在的位置赋值为其他元素的乘积,而其他位置依然为0,返回即可。
    2. 长度大于2但含有不止一个0,例如[9 0 0 3]这样的数组,我们容易证明对于这样的数组,要返回的数组的所有元素应该都为0。

Corner case讨论完毕,下面我们看代码:

/*solution1 60ms*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int i=0,res=1,count=0,zero_pos=0;
        vector<int> output(nums.size(),0);
        for(i=0;i<nums.size();i++)
            res=res*nums[i];
        if(!res){
            if(nums.size()==2){
                swap(nums[0],nums[1]);
                return nums;
            }
            else if(nums.size()>2){
                res=1;
                /*计算除0以外所有元素的乘积,并记录0的个数和位置*/
				for(i=0;i<nums.size();i++){
                    if(nums[i]==0){
                        count++;
                        zero_pos=i;
                        continue;
                    }
                    res=res*nums[i];
                }
                if(count==1){
                    output[zero_pos]=res;
                    return output;
                }
                if(count>1)
                    return output;
            }
        }
        for(i=0;i<nums.size();i++)
            output[i]=res/nums[i];
        return output;
    }
};

在参阅了讨论区之后,发现之前对题意的理解上有一点偏差。提示中说”without division”,我理解成了“不能对数组进行分割”,但这道题想表达的意思可能是“不能用除法”,所以上面的解法可能不够完美。

于是转换思路,假如有一个数组为[a,b,c,d],那么在经过这样一轮运算后得到的结果就是[bcd,acd,abd,abc],所以我们可以构造这样两个数组[1,a,ab,abc]和[bcd,cd,d,1].这样两个数组对应项相乘就可以得到结果。代码如下:

/*solution2 60ms*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> arr1(nums.size(),1);
        vector<int> arr2(nums.size(),1);
        for(int i=1;i<arr1.size();i++)
            arr1[i]=arr1[i-1]*nums[i-1];
        for(int i=arr2.size()-2;i>=0;i--)
            arr2[i]=arr2[i+1]*nums[i+1];
        for(int i=0;i<arr1.size();i++)
            arr1[i]=arr1[i]*arr2[i];
        return arr1;
    }
};

但是题目要求除了output这个要返回的数组外,空间复杂度必须为O(1),所以我们不能开两个数组,必须采用滚动计算的方法来替换其中的一个数组。代码如下:

/*solution3 60ms*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> arr1(nums.size(),1);
        int tmp=1;
        for(int i=1;i<arr1.size();i++)
            arr1[i]=arr1[i-1]*nums[i-1];
        for(int i=nums.size()-1;i>=0;i--){
            arr1[i]=arr1[i]*tmp;
            tmp=tmp*nums[i];
        }
        return arr1;
    }
};

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这道题的思路其实也被应用于missing number中,就是采用异或操作,如果只有一个元素只出现过一次,那么对所有元素采用异或操作后得到的就是single number,代码如下:

/*use bit manipulation 20ms,no extra place*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int i=0,single=0;
        for(i=0;i<nums.size();i++)
            single^=nums[i];
        return single;
    }
};

时间复杂度为O(n),空间复杂度O(1),符合题目要求

对于这个题而言,另一种解法是使用hash-table,先建立哈希表,然后遍历数组中的元素,如果该元素不在表中,则将其插入表中;否则将其删除,最后返回表中唯一一个元素即可,代码如下:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        int i=0,single;
        for(i=0;i<nums.size();i++){
            if(hash.find(nums[i])==hash.end())
                hash[nums[i]]=i;
            else
                hash.erase(nums[i]);
        }
        unordered_map<int,int>::iterator it=hash.begin();
        return (*it).first;
    }
};

时间复杂度为O(n),空间复杂度为O(n)