BM18 二维数组中的查找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row=array.size();
        if(row==0||array[0].size()==0) return false;
        for(int i=0;i<row;i++){
            int right=array[0].size();
            int left=0;
            int mid=(right+left)/2;
            while(left<=right){
                if(array[i][mid]==target){
                    return true;
                }else if(array[i][mid]>target){
                    right=mid-1;
                    mid=(left+right)/2;
                }else{
                    left=mid+1;
                    mid=(left+right)/2;
                }
            }
        }
        return false;
    }
};

BM19 寻找峰值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        // write code here
        for(int i=1;i<nums.size();i++){
            if(nums[i-1]>nums[i]||nums[i-1]==nums[i]){
                return i-1;
            }
        }
        return nums.size()-1;
    }
};

BM20 数组中的逆序对

归并排序的思路：在归并排序过程中会将数组划分成最小2个元素的子数组，然后一次比较子数组的长度，这里我们也可以用相同的方法统计逆序对。

  1. 划分阶段：将待划分区间从重点划分为两部分；
  2. 排序阶段：使用归并排序递归处理子序列，同时统计逆序对；
  3. 合并阶段：将拍好序的子序列合并；

因为在归并排序中，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。

class Solution {
public:
    int mod = 1000000007;
    int mergeSort(int left, int right, vector<int>& data, vector<int>& temp){
        if (left >= right)    // 停止划分
            return 0;
        int mid = (left + right) / 2; //取中间
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //左右划分
        res %= mod;  //防止溢出
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++)
            temp[k] = data[k];
        for (int k = left; k <= right; k++) {
            if (i == mid + 1)
                data[k] = temp[j++];
            else if (j == right + 1 || temp[i] <= temp[j])
                data[k] = temp[i++];
            else { //左边比右边大，答案增加
                data[k] = temp[j++];
                res += mid - i + 1; // 统计逆序对
            }
        }
        return res % mod;
    }
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> res(n);
        return mergeSort(0, n - 1, data, res);
    }
};

BM21 旋转数组的最小数字

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
    }
};

BM22 比较版本号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    int compare(string version1, string version2) {
        // write code here
        int i=0,j=0,len1=version1.size(),len2=version2.size();
        while(true){
            long long pa=0,pb=0;
            while(i<len1){
                if(version1[i]=='.'){
                    i++;
                    break;
                }else{
                    pa=pa*10+version1[i]-'0';
                }
                i++;
            }
            while(j<len2){
                if(version2[j]=='.'){
                    j++;
                    break;
                }else{
                    pb=pb*10+version2[j]-'0';
                }
                j++;
            }
            if(pa>pb) return 1;
            if(pa<pb) return -1;
            if(i==len1&&j==len2) return 0;
        }
    }
};