第16章 模拟

下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须** 原地 **修改，只允许使用额外常数空间。

标准的“下一个排列”算法可以描述为：

1. 从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
2. 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3. 将 A[i] 与 A[k] 交换
4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

该方法支持数据重复，且在 C++ STL 中被采用。

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1){
            return;
        }
        int i = nums.length - 2;
        for(; i >= 0 && nums[i] >= nums[i + 1]; i--);
        if(i == -1){
            reverse(nums, 0, nums.length - 1);
        }else{
            int j = nums.length - 1;
            for(; nums[i] >= nums[j]; j--);
            swap(nums, i, j);
            reverse(nums, i + 1, nums.length - 1);
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int i, int j){
        while(i < j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

区间问题

LC57：插入区间

给你一个 无重叠的 *，*按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{{newInterval[0], newInterval[1]}};
        }

        List<int[]> list = new ArrayList<>();
        int index = 0;
        // 步骤一：找到需要合并的区间
        while (index < intervals.length && intervals[index][1] < newInterval[0]) {
            list.add(intervals[index++]);
        }
        // 步骤二：合并区间
        while (index < intervals.length && intervals[index][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
            index++;
        }
        list.add(newInterval);
        // 步骤三：处理合并区间之后的区间
        while (index < intervals.length) {
            list.add(intervals[index++]);
        }
        return list.toArray(new int[list.size()][]);
    }
}