归并

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

 

示例 1:

输入: [7,5,6,4]
输出: 5
 

限制:

0 <= 数组长度 <= 50000
class Solution {
public:
    int reversePairs(vector<int> &nums) {
        int ans = 0;
        merge_sort(nums, 0, nums.size() - 1, ans);
        int a;
        return ans;
    }

    void merge_sort(vector<int> &nums, int left, int right, int &ans) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            merge_sort(nums, left, mid, ans);
            merge_sort(nums, mid + 1, right, ans);
            merge(nums, left, mid, right, ans);
        }
    }

    void merge(vector<int> &nums, int left, int mid, int right, int &ans) {
        vector<int> temp;
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                temp.push_back(nums[j++]);
                ans += mid - i + 1;//和归并排序唯一不同的地方
            } else
                temp.push_back(nums[i++]);

        }
        //下面两个循环只有一个会执行
        while (i <= mid)
            temp.push_back(nums[i++]);
        while (j <= right)
            temp.push_back(nums[j++]);
        for (int i = 0; i < temp.size(); i++)
            nums[left + i] = temp[i];
    }
};

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

给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
import java.util.*;

public class Threehundred_fifteen {
    /**
     * 对于数组 a[lo..hi),如果 a[lo..mid) 与 a[mid..hi) 都已经归并有序,则:
     * 对于左半区间中 a[lo..mid) 中的每个元素 a[left],计算 a[mid..hi) 中有多少个元素小于它。
     */
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            ans.add(0);
        }
        int[][] index = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            index[i] = new int[]{nums[i], i};
        }
        merge_sort(index, 0, index.length, ans);
        return ans;
    }

    public void merge_sort(int[][] index, int start, int end, List<Integer> ans) {
        if (end - start <= 1)
            return;
        int mid = start + (end - start) / 2;
        merge_sort(index, start, mid, ans);
        merge_sort(index, mid, end, ans);
        int right = mid;
        // 对于左半区间中的每个元素left,统计右侧比它小的元素的个数
        for (int i = start; i < mid; i++) {
            while (right < end && index[i][0] > index[right][0])
                right++;
            ans.set(index[i][1], ans.get(index[i][1]) + right - mid);
        }
        Arrays.sort(index, start, end, new Comparator<int[]>() {//相当于归并排序中合并左右区间,end不包含在内
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
    }
}

327. 区间和的个数

给定一个整数数组 nums,返回区间和在 [lower, upper] 之间的个数,包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ,请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3 
解释: 3个区间分别是: [0,0], [2,2], [0,2],它们表示的和分别为: -2, -1, 2。
mport java.util.*;

public class Threehundred_twentySeven {
    public int merge_sort(List<Long> list, int start, int end, int lower, int upper) {
        if (end - start <= 1)
            return 0;
        int mid = start + (end - start) / 2;
        int cnt = merge_sort(list, start, mid, lower, upper) + merge_sort(list, mid, end, lower, upper);
        int right1 = mid;
        int right2 = mid;
        for (int i = start; i < mid; i++) {
            // 统计右侧-nums[left] < lower 的个数
            while (right1 < end && list.get(right1) - list.get(i) < lower)
                right1++;
            // 统计右侧-nums[left] <= upper 的个数
            while (right2 < end && list.get(right2) - list.get(i) <= upper)
                right2++;
            // 因此右侧-nums[left]的差在 [lower,upper] 的个数为:
            //count += (right2 - mid) - (right1 - mid); 可以简写为下面这样
            cnt += right2 - right1;
        }
        Collections.sort(list.subList(start, end));
        return cnt;
    }

    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0)
            return 0;
        List<Long> list = new ArrayList<>();
        list.add(Long.valueOf(0));
        // 计算前缀和
        for (int i = 0; i < nums.length; i++) {
            list.add(list.get(i) + nums[i]);
        }
        return merge_sort(list, 0, list.size(), lower, upper);
    }
}
0