数组（9-11）

二维数组中的查找

思路：抓住左下角的数，比它大就往右，比它小就往上（之后的每一个数都是这样）知道超出了数组边界
步骤：
1.先求出数组的场和宽（便于定位左下角的元素以及判断边界）
2.从左下角的元素开始遍历，比它大就往右，比它小就往上，相等就是找到了，返回1
3.判断边界，超出边界了则是没有找到，返回0

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int m=array.size();
        int n=array[0].size();
        int i=m-1;
        int j=0;
        while(i>=0&&j<n)
        {
            if(array[i][j]<target)
                j++;
            else if(array[i][j]>target)
                i--;
            else return 1;
        }
        return 0;
    }
};

把数组排成最小的数

思路：关键在于若a+b>b+a，则把b放在前面（考虑一下定义仿函数，用sort算法进行自定义排序）
sort算法中可以利用仿函数自己定义排序规则

class myCompare
{
public:
    bool operator()(const string& str1, const string& str2)
    {
        return str1 + str2 < str2 + str1;
    }
};

class Solution {
public:
    string PrintMinNumber(vector<int> numbers)
    {
        vector<string> str_numbers;
        string str = "";
        for (int i = 0; i < numbers.size(); i++)
        {
            str_numbers.push_back(to_string(numbers[i]));
        }
        sort(str_numbers.begin(), str_numbers.end(), myCompare());
        for (int i = 0; i < numbers.size(); i++)
        {
            str += str_numbers[i];
        }
        return str;
    }
};

数组中的逆序对

思路1(暴力求解)：对于数组中的每一个元素依次找它后面比它大的元素，统计个数
这种方法的时间复杂度是O(n2)，只AC了50%
可以考虑一下归并排序的思路进行改进

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

加上下面这句，AC了75%

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

思路2：采用归并排序的变法，在Merge过程中，数后面有几个元素比它大（一开始也只有50%，后来加了count%1000000007变为了75，再加一个变成100%）不知道什么原因，可能是数字太大，在函数传递过程中会发生错误，所以需要在函数中把它进行取余。但是在暴力求解中没法100%

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<2)
            return 0;
        int l=0;
        int r=data.size()-1;
        int count=process(data,l,r);
        //if(count>=1000000007)
         //   count=count%1000000007;这句加不加无所谓
        return count;

    }
public:
    int process(vector<int> &data,int l,int r)
    {
        if(l==r)
            return 0;
        int m=(l+r)/2;
        int count=process(data,l,m)+process(data,m+1,r)+merge(data,l,m,r);
        if(count>=1000000007)
            count=count%1000000007;//不加这句75%
        return count;
    }
    int merge(vector<int> &data,int l,int m,int r)
    {
        vector<int> v;
        int count=0;
        int i=l;
        int j=m+1;
        while(i<=m&&j<=r)
        {
            if(data[i]>data[j])
            {
                v.push_back(data[i]);
                count+=r-j+1;
                if(count>=1000000007)
                    count=count%1000000007;//不加这句50%
                i++;
            }
            else
            {
                v.push_back(data[j]);
                j++;
            }
        }
        while(i<=m)
        {
            v.push_back(data[i++]);
        }
        while(j<=r)
        {
            v.push_back(data[j++]);
        }
        for(i=0;i<v.size();i++)
        {
            data[l+i]=v[i];
        }
        return count;
    }
};