一、数组中的逆序对

解法一:归并排序(推荐)

• 先划分，将带划分区间，从中点一分为二
• 再排序,使用归并排序递归处理子序列，同时统计逆序对
• 最后合并，合并排序好的子序列，同时累加逆序对数
  

class Solution {
    
public:
    const int mod=1000000007;
    int MergeSort(vector<int>&data,vector<int>&tmp,int left,int right)
    {
    
        if(left>=right)
            return 0;
        int mid=(left+right)/2;
        int ret=MergeSort(data, tmp, left, mid)+MergeSort(data, tmp, mid+1, right);//划分左右区间
        ret%=mod;//防止数据溢出
        int i=left,j=mid+1;
        for(int k=left;k<=right;k++)//将区间值赋给tmp
            tmp[k]=data[k];
        for(int k=left;k<=right;k++)//对data区间内数据进行排序，同时统计逆序数，这里用赋值排序
        {
    
            if(i==mid+1)//i即左边界已走到中间节点，右边界直接赋值过来
                data[k]=tmp[j++];
            else if(j==right+1||tmp[i]<=tmp[j])//j已走到右边界或者左边值较小时，将左边值赋给data
                data[k]=tmp[i++];
            else
            {
    
                data[k]=tmp[j++];//反之代表左边比右边大，逆序
                ret+=mid-i+1;//累计逆序数
            }
        }
        return ret%mod;
    }
    int InversePairs(vector<int> data) {
    
        vector<int>v(data.size());
        return MergeSort(data,v,0,data.size()-1);
    }
};

时间复杂度:O(n${\log }_2$n),利用归并排序的分治思想
空间复杂度:O(n),tmp辅助数组长度为n，递归栈最大深度不超过n

解法二:树状数组

• 将原数组离散化，经排序和二分查找映射，将数组[100 50 2000 4 3]映射为[4 3 5 2 1],使它们相连，减少空间需求.
• 从前往后遍历每个元素，查找在树状数组里的前缀和，表示该元素在树状数组中出现过多少次，前缀和做差，表示值在[array[i]+1,m]中出现的次数，即逆序数

class BIT {
    
private:
    vector<int> tree;
    int n;
    
public:
    //初始化树状数组的大小
    BIT(int m) : n(m), tree(m + 1) {
    } 
    //使数组呈现2、4、8、16这种树状
    int lowbit(int x){
     
        return x & (-x);
    }
    //查询序列1到x的前缀和
    int query(int x){
     
        int ret = 0;
        while(x){
    
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }
    //序列x位置的数加1
    void update(int x){
     
        while(x <= n){
    
            tree[x]++;
            x += lowbit(x);
        }
    }
};
class Solution {
    
public:
    const int mod = 1000000007;
    int InversePairs(vector<int> data) {
    
        int n = data.size(),ret=0;
        vector<int> tmp = data;
        //排序得到一份有序的数组
        sort(tmp.begin(), tmp.end());
        //二分法重新映射，将数字变成其在有序数组中的位置
        for(int i = 0; i < n; i++) 
            //二分法查找在其在有序数组中的位置
            data[i] = lower_bound(tmp.begin(), tmp.end(), data[i]) - tmp.begin() + 1;
        //建立大小为n的树状数组
        BIT bit(n); 
        //统计逆序对
        for(int i = 0; i < n; i++){
     
            //前缀和做差
            ret = (ret + bit.query(n) - bit.query(data[i])) % mod;
            bit.update(data[i]);
        }
        return ret;
    }
};

lowbit()函数用来取一个二进制最低位的一与后边的0组成的数
例：5（101），lowbit(5)=1（1）
12（1100），lowbit(12)=4（100）
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
不同在于lower_bound()包含目标值，查找大于等于或小于等于该值的数据(可用仿函数或内建函数对象指定查找方式)，upper_bound()不包含，只取大于或小于该值的数据，这是库中内置的二分查找函数。
时间复杂度:O(n${\log }_2$n),sort排序函数O(n${\log }_2$n)，二分法O(${\log }_2$n)，分n次，
查询更新都为O(${\log }_2$n)，共n次
空间复杂度:O(n),tmp辅助数组长度为n，数状数组长度为n

解法三:遍历

class Solution {
    
public:
    const int mod=1000000007;
    int InversePairs(vector<int> data) {
    
        int ret=0,n=data.size();
        for(int i=0;i<n;i++)
        {
    
            for(int j=i+1;j<n;j++)
                if(data[i]>data[j])
                {
    
                    ret+=1;
                    ret%=mod;
                }
        }
        return ret;
    }
};

没啥可说的
时间复杂度:O(n^2)
空间复杂度:O(1)
运行超时

二、 旋转数组的最小值

解法一:二分法(推荐)

根据题目要求旋转数组是将原本有序的数组分成了两部分有序的数组，在原始数组中最小的元素一定是在首位，那么旋转后无序的点即为最小的数字。

• 用双指针分别指向旋转后数组的首尾
• 若区间中点值大于右界值，则最小值一定在中点右边
• 若中点值等于区间右界值，则难以分辨最小数字在哪个区间，如[1,1,1,0,1],要逐个缩减右界
• 中点值小于区间右界值，则最小值一定在中点左边
• 通过调整区间锁定最小值

class Solution {
    
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
    
        int left=0,right=rotateArray.size()-1;
        while(left<right)
        {
    
            int mid=(left+right)/2;
            if(rotateArray[mid]>rotateArray[right])
                left=mid+1;
            else if(rotateArray[mid]<rotateArray[right])
                right=mid;//存在中点即为最小值的可能，要保留
            else
                right--;//逐个缩减右区间
        }
        return rotateArray[left];
    }
};

时间复杂度:O(${\log }_2$n)
空间复杂度:O(1)

解法二:遍历

就找最小值

class Solution {
    
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
    
        int min=rotateArray[0];
        for(int i=0;i<rotateArray.size();i++)
            if(min>rotateArray[i])
                min=rotateArray[i];
        return min;
    }
};

时间复杂度:O(n)
空间复杂度:O(1)

三、比较版本号

解法一:双指针(推荐)

基于题目描述，因为数字前导0采用字符对比比较麻烦，因此采用数字转化比较

• 利用两个指针表示两字符串下标，遍历两字符串
• 每次截取‘.’号之前的数字字符组成数字，之前的数字乘10再加上当前数字，考虑溢出，采用long long类型存储
• 然后比较两数大小

class Solution {
    
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 比较版本号 * @param version1 string字符串 * @param version2 string字符串 * @return int整型 */
    int compare(string version1, string version2) {
    
        // write code here
        int len1=version1.size(),len2=version2.size(),i=0,j=0;
        while(i<len1||j<len2)
        {
    
            long long n1=0;
            while(i<len1&&version1[i]!='.')//在点之前截取数字
            {
    
                n1=n1*10+version1[i]-'0';
                i++;
            }
            i++;//跳过点号
            long long n2=0;
            while(j<len2&&version2[j]!='.')
            {
    
                n2=n2*10+version2[j]-'0';
                j++;
            }
            j++;
            if(n1>n2)//每过一个点比较一次
                return 1;
            if(n1<n2)
                return -1;
        }
        return 0;//直到最后都相同，表明相等
    }
};

时间复杂度:O(max(n,m)),即长度最长的字符串
空间复杂度:O(1)

解法二:分割截取

• 利用c++的istringstream流输入，以字符点将两个原字符串分割，使每个修订号的数字单独呈现在数组中
• 遍历数组，每次各取一个数字比较，较短的直接追加取0
• 遍历取出的数字字符串，转换为数字，比较数字大小

class Solution {
    
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 比较版本号 * @param version1 string字符串 * @param version2 string字符串 * @return int整型 */
    int compare(string version1, string version2) {
    
        // write code here
        vector<string>num1,num2;
        istringstream s1(version1);
        istringstream s2(version2);
        string tmp;
        while(getline(s1,tmp,'.'))//流输入分割
            num1.push_back(tmp);
        while(getline(s2,tmp,'.'))
            num2.push_back(tmp);
        for(int i=0;i<num1.size()||i<num2.size();i++)
        {
    
            long long n1=0,n2=0;
            string str1=i<num1.size()?num1[i]:"0";//不足追加0
            string str2=i<num2.size()?num2[i]:"0";
            for(int j=0;j<str1.size();j++)
                n1=n1*10+str1[j]-'0';
            for(int j=0;j<str2.size();j++)
                n2=n2*10+str2[j]-'0';
            if(n1>n2)
                return 1;
            if(n1<n2)
                return -1;
        }
        return 0;
    }
};

时间复杂度:O(max(n,m))，因为在根本上只是遍历字符串
空间复杂度:O(max(n,m)),最坏长度为字符串长度的最大值