算法专题七: 分治归并

1. 排序数组

算法思路: 本道题使用归并的思路进行排序, 先讲数组分为左右两个区间, 然后合并两个有序数组.

class Solution {
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.reserve(nums.size());
        mergesort(nums,0,nums.size()-1);
        return nums;
    }
    void mergesort(vector<int>& nums,int left,int right)
    {
        if(left >= right) return;
        int mid = (right + left)>>1;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int i = left; i <= right;i++)
        {
            nums[i] = tmp[i - left];
        }
    }
};

2. 交易逆序对的总数

算法思路:

先找左半部分的逆序对, 然后再找右半部分的逆序对, 最后再一左一右的找逆序对, 找完左半部分和右半部分之后给数组排个序对数组的结果不影响, 而且排完序之后找一左一右的逆序对还简单些, 不由得我们就可以想到此方法和归并排序的思路一样, 只不过再排序的过程中增加了统计逆序对的个数. 这里可以采用两种策略, 第一种固定当前位置的值, 然后找前面有多少数是比我大的, 第二种策略, 固定当前位置的值, 找后面有多少元素是比我小的.

• 首先使用第一种策略, 固定一个数, 在前面找比我大的元素的个数.

当前为升序的排序, 我们归并的时候如果nums[cur1] <= nums[cur2] 时, 此时我们只需要把cur1++就行, 如果nums[cur1]在某一个位置大于nums[cur2]时,此时已经找到了比nums[cur2]大的元素, 那么mid- cur1 + 1这段区间里面的所有值都比nums[cur2]大, 此时统计逆序对的数量即可, 然后再让cur2++, 但是不要往了我们还要排序, 所以这一步写在归并数组那里即可.
那么既然升序可以, 降序可不可以呢?

如图所示, 该数组为降序的时候, 固定cur1, cur2位置时,如果cur1大于cur2则开始统计cur1中大于cur2元素的个数, 看似没有什么问题, 但是如果进入下一次循环中, cur1++之后还有可能大于cur2,此时在统计那不是重复了嘛, 显然结果是错误的

• 第二种策略: 固定一个数, 然后找后面比我小的元素的个数

首先先来看降序的数组, 来统计固定一个位置之后, 后面有多少元素比我小, 当nums[cur1] <= nums[cur2]时, 此时不是我们想要的结果, 我们需要的是nums[cur1]>nums[cur2], 这个时候, 我们统计后面有多少个元素比我小即可, 很显然此时数组是降序的, 所以right - cur2 + 1 即为结果

if(nums[cur1] <= nums[cur2])
tmp[i++] = nums[cur2++];
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}

反之我们来看一下升序

此时数组为升序, 我们需要找后面比前面小的元素的个数, 当固定到cur1之后, nums[cur1] > nums[cur2]时, 此时开始找结果, 在后面看在mid到cur2之间的这部分都是比nums[cur1]小的, 但是下一次cur2++之后还有可能是小于nums[cur1]的, 所以此时重复统计了 , 结果是错误的.

代码部分:

策略1

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& record) {
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return 0;
        int ret = 0;
        int mid = (right + left) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        //程序到这里左边与右边已经处理完毕, 现在处理左右
        int cur1 = left, cur2 = mid + 1, i = 0;
        //升序 找比当前位置大的个数
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            else
            {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++]; 
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }
        return ret;
    }
};

策略2

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& record) {
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return 0;
        int ret = 0;
        int mid = (right + left) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        //程序到这里左边与右边已经处理完毕, 现在处理左右
        int cur1 = left, cur2 = mid + 1, i = 0;
        //降序 找比当前位置小的个数
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur2++];
            else
            {
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++]; 
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }
        return ret;
    }
};

3. 计算右侧小于当前元素的个数

算法思路:

本道题更上一道题的思路是一模一样的, 上一道题我们采用了策略一的方法, 本道题我们采用策略二, 找后面比当前位置元素小的元素的个数, 但是与上一道题不同的是本道题要求返回对应位置的结果, 这是个问题, 如何解决呢, 我们可以采用哈希的思想, 如果使用哈希表那么如果遇到重复的元素, 我们就无法进行解决, 但是我们可以采用这种思想, 创建一个新的数组, 这个数组中存放的是对应位置原始的下标, 然后这个数组跟着nums一起变化, 但是无论怎样变换, 里面的下标还是最原始的下标位置.

编写代码:

class Solution {
    vector<int> index;
    vector<int> ret;
    int tmpNums[500010];
    int tmpIndxt[500010];
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        for(int i = 0;i < n;i++)
            index[i] = i;
        mergeSort(nums,0,n-1);
        return ret;
    }
    void mergeSort(vector<int>& nums,int left,int right)
    {
        if(left >= right) return;
        int mid = (left + right)>>1;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //至此左右已经处理完, 现在处理一左一右
        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmpNums[i] = nums[cur2];
                tmpIndxt[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndxt[i++] = index[cur1++];
            }
        }
        while(cur1 <= mid)
        {
            tmpNums[i] = nums[cur1];
            tmpIndxt[i++] = index[cur1++];
        }
        while(cur2 <= right)
        {
            tmpNums[i] = nums[cur2];
            tmpIndxt[i++] = index[cur2++];
        }
        for(int i = left; i <= right; i++)
        {
            nums[i] = tmpNums[i - left];
            index[i] = tmpIndxt[i - left];
        }
    }
};

4. 翻转对

算法思路:

首先我们还是先考虑两个策略. 策略一, 计算后面有多少个元素的两倍比我小, 策略二. 计算前面有多少元素的一半比我大. 不同于前两题, 本道题无法在归并的时候进行计算, 因为这里的比较逻辑和归并的比较逻辑是不同的, 所以这里我在归并逻辑之前采用双指针的方法先进行统计, 然后在进行归并排序.

那么首先来看策略一, 在处理完左右之后并排序之后, 我们处理一左一右的情况, 使用双指针, 计算后面有多少元素的两倍比我小, 如果nums[cur1] <= nums[cur2] * 2, 则说明后面元素的两倍比我大, 那么继续移动cur2, 知道找到cur2的位置两倍比我小, 然后进行统计, 此时cur1++, 进行下一次的统计, 这里cur2还需要回退到mid+1的位置嘛?
答案是不需要的, 因为当前位置cur2位置前面元素的两倍都是比我大的, 那cur1++之后降序, 那么一定也是比我大的, 所以直接统计就可以了, 所以整体的时间复杂度为O(NlogN).

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0 , nums.size() - 1);
    }
    int mergeSort(vector<int>&nums, int left , int right)
    {
        if(left >= right) return 0;
        int ret = 0;
        int mid = (left + right) >> 1;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if(cur2 > right) break;//小优化
            ret += right - cur2 + 1;
            cur1++;
        }
        //降序
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while(cur1<=mid) tmp[i++] = nums[cur1++];
        while(cur2<=right) tmp[i++] = nums[cur2++];
        for(int j = left; j <= right; j++)
            nums[j] = tmp[j]; 
        return ret;
    }
};

策略二: 找前面有多少元素的一半比我大

其实更策略一的逻辑是类似的, 只不过这里的数组是升序排列的, 找前面有多少元素的一半比我大, 先让cur1走, 如果/2之后大于nums[cur2]则, cur1++, 找到位置之后统计ret, 然后让cur2++,进行下一次的统计, 此时cur1也不需要回去, cur1之前的位置一半都是比cur2小的, 那么cur2++之后一定还是比cur1小, 所以cur2直接++即可.

class Solution {
    int tmp[50000];
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size()-1);
    }
    int mergeSort(vector<int>& nums,int left, int right)
    {
        if(left >= right) return 0;
        int mid = (left + right) >> 1;
        int ret = 0;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);
        int cur1 = left, cur2 = mid + 1, i = left;
        //升序, 先统计逆序对
        while(cur2 <= right)
        {
            while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;
            if(cur1 > mid) break;
            ret += mid - cur1 + 1; 
            cur2++;
        } 
        //合并有序数组
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int j = left ; j <= right ; j++)
            nums[j] = tmp[j];
        return ret;
    }
};

完