Leetcode-31

题目

运行结果

四个月前

四个月后

代码

四个月前

package eternal.fire.java;

import java.util.*;

public class LeetCode {
    // 测试
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{1, 2, 3};
        solution.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}

class Solution {
    // 核心函数
    public void nextPermutation(int[] nums) {
        // 从数组中倒数第二个元素开始从后往前找起
        for (int i = nums.length - 2; i >= 0; i--) {
            int position = theOne(nums, i);
            if (position != -1) {
                // 交换位置
                swap(nums, i, position);
                // 将后面的部分排序以保证是最小的
                Arrays.sort(nums, i + 1, nums.length);
                break;
            }
            // 如果没有找到更大的排列方式
            if (i == 0) {
                reverse(nums);
            }
        }
    }

    /**
     * 交换数组中的元素
     *
     * @param nums 数组
     * @param i    下标1
     * @param j    下标2
     */
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 找到比nums[index]大的数，返回最小的一个符合条件的数的下标
     * @param nums 数组
     * @param index 下标
     * @return 返回最小的一个符合条件的数的下标
     */
    public int theOne(int[] nums, int index) {
        // 初始化
        int val = -1;
        int position = -1;
        // 给val和position一个初始值
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[index] < nums[i]) {
                val = nums[i];
                position = i;
                break;
            }
        }
        // 没有合适的可交换对象
        if (position == -1) {
            return -1;
        }
        // 更新val和position的值确保其是最合适的
        for (int i = position; i < nums.length; i++) {
            if (nums[i] > nums[index]) {
                if (nums[i] < val) {
                    position = i;
                    val = nums[i];
                }
            }
        }
        return position;
    }

    /**
     * 翻转数组
     * @param nums 数组
     */
    public void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

ps：没看题解，不知道自己是否最优。

四个月后

class Solution {
    public void nextPermutation(int[] nums) {
        if (isDecrease(nums)) {
            Arrays.sort(nums);
            return;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = biggerThanMe(nums, i);
            if (index != 0) {
                swap(nums, i, index);
                Arrays.sort(nums, i + 1, nums.length);
                return;
            }
        }
    }

    private boolean isDecrease(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                return false;
            }
        }
        return true;
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    private int biggerThanMe(int[] nums, int index) {
        int me = nums[index];
        int target = Integer.MAX_VALUE;
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] > me) {
                target = Math.min(target, nums[i]);
            }
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return 0;
    }
}

看了一下之前写的，现在的思路和之前的基本一样，稍有改动。

复杂度

时间复杂度：O（NlogN）

空间复杂度：O（1）