专栏首页曌的晓痴LeetCode-下一个排列

LeetCode-下一个排列

感觉从之前的题目开始写起来的话,会需要一定的时间去思考当时为什么这么写,那么每次写都是重新思考,除非进度能够赶上最新的刷题进度,所以决定从最新的开始往前写....最近又一直在刷LeetCode中文官网的题目,毕竟英语题目理解能力捉鸡。

原题地址: https://leetcode-cn.com/problems/next-permutation/

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

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

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

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

解题思路:

这题一开始我想错了方向,以为从右往左找到第一个值变小的索引后,将后续的元素排序即可,后来证明并不是这样的。正确的思路应该是:

  1. 从右往左遍历,找到第一个值变小的索引i
  2. 如果i等于-1,说明当前的数字序列是递减的,也就是没有更大的序列了,那么将整个数组反转即可,也就是变成最小的序列
  3. 如果i大于等于0,那么就需要从右往左找到比nums[i]大的第一个元素,然后将nums[i]和该元素交换位置,再将坐标i之后的所有元素反转,也就是将坐标i之后的序列由最大变为最小。

通过以上三步,最终完成找到数组下一个排列的功能。

第3步中,之所以需要找刚好比nums[i]大的第一个元素,就是为了获得比当前排列恰好更大一级的排列。

如果有兴趣的话,可以看看LeetCode上关于这题的别人的一些题解:

中文:

https://leetcode-cn.com/problems/next-permutation/solution/

英文:

https://leetcode.com/problems/next-permutation/solution/

个人题解:

 public void nextPermutation(int[] nums) {
       // 从右往左遍历,找到值变小的索引
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        // 如果i>=0,从右往左找,找到值比nums[i]大的最小的值,交换
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        // 将nums中i之后的所有元素都逆转一下
        i += 1;
        int j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }

结果:

这题横跨了我两周的时间,然后由于本地代码没有提交到git,所以在我重装系统之后,一切记忆重新开始,最后成功的在失败了5次之后,将这题给解了出来,最后结果还算不错。

本文分享自微信公众号 - 曌的晓痴(gh_543795945efe),作者:zxyAnkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 4数之和

    今天才发现,上周在钉钉上面加我的阿里同学,就是给我发offer的HR,而我当时并不知道,只知道去骚扰其他的HR问结果。

    晓痴
  • LeetCode - 存在重复元素

    原题地址:https://leetcode-cn.com/problems/contains-duplicate/

    晓痴
  • LeetCode - 搜索插入位置

    LeetCode第35题,难度简单。接下去的题目可能会慢慢变成两三年之前做的题目了....清完库存我再接着解题,写题解...

    晓痴
  • python实现给定一个数和数组,求数组

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    py3study
  • 283 Move Zeroes

    /** * 题意:将0挪到末尾,并且不改数组中原有元素的顺序 * 解析:找到0元素,然后寻找其后面非0的元素,进行交换位置 * @param {numbe...

    用户1624346
  • Leetcode 15 三数之和(双指针,去重)

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    glm233
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • 【剑指Offer】调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    小新哟
  • LeetCode-31-Next-Permutation

    这个排序主要是有两种情况,一个是类似于3 1 2这样的情况,直接从后往前找到第一个nums[i]<nums[i-1]的,然后把i记下来,再与后面第一个小于i的k...

    小二三不乌

扫码关注云+社区

领取腾讯云代金券