C++实现LeetCode(31.下一个排列)

[LeetCode] 31. Next Permutation 下一个排列

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

这道题让我们求下一个排列顺序，由题目中给的例子可以看出来，如果给定数组是降序，则说明是全排列的最后一种情况，则下一个排列就是最初始情况，可以参见之前的博客 Permutations。再来看下面一个例子，有如下的一个数组

1　　2　　7　　4　　3　　1

下一个排列为：

1　　3　　1　　2　　4　　7

那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后再从后往前找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字转置一下即可，步骤如下：

1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1

1　　3　　7　　4　　2　　1

1　　3　　1　　2　　4　　7

解法一：

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int i, j, n = num.size();
        for (i = n - 2; i >= 0; --i) {
            if (num[i + 1] > num[i]) {
                for (j = n - 1; j > i; --j) {
                    if (num[j] > num[i]) break;
                }
                swap(num[i], num[j]);
                reverse(num.begin() + i + 1, num.end());
                return;
            }
        }
        reverse(num.begin(), num.end());
    }
};

下面这种写法更简洁一些，但是整体思路和上面的解法没有什么区别，参见代码如下：

解法二：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {int n = nums.size(), i = n - 2, j = n - 1;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        if (i >= 0) {
            while (nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

到此这篇关于C++实现LeetCode(31.下一个排列)的文章就介绍到这了,更多相关C++实现下一个排列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • C++实现LeetCode(21.混合插入有序链表)

    [LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2

  • C++实现LeetCode(28.实现strStr()函数)

    [LeetCode] 28. Implement strStr() 实现strStr()函数 Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 E

  • C++实现LeetCode(25.每k个一组翻转链表)

    [LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of n

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(27.移除元素)

    [LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with

  • C++实现LeetCode(22.生成括号)

    [LeetCode] 22. Generate Parentheses 生成括号 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", &qu

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • Java全排列算法字典序下的下一个排列讲解

    一直写过数组全排列的算法,当时接触的是使用回溯的方法,这样可以保证生成的全排列一定是按照字典序的,但是今天在做leetcode上的一道题时,问题是要你找到某个排列情况的下一个按照字典序排列的状态. 如果直接一点,大可从头开始做全排列,然后到目标状态时,在做一次即可找到要的状态,但是如果题目给的状态非常靠后,则要花费很大的代价,这样做就显得有些笨拙了. 所以做这道题的时候一直在思考如何按照字典序生成全排列. 假设此时给出的状态时5 2 4 3 1,那么下一个状态要如何确定呢?首先从人的视角来看,绝

  • C++实现LeetCode(74.搜索一个二维矩阵)

    C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • Go语言LeetCode题解937重新排列日志文件

    目录 一 题目描述 二 分析 三 答案 一 题目描述 937. 重新排列日志文件 - 力扣(LeetCode) (leetcode-cn.com) 给你一个日志数组 logs.每条日志都是以空格分隔的字串,其第一个字为字母与数字混合的 标识符 . 有两种不同类型的日志: 字母日志:除标识符之外,所有字均由小写字母组成 数字日志:除标识符之外,所有字均由数字组成 请按下述规则将日志重新排序: 所有 字母日志 都排在 数字日志 之前. 字母日志 在内容不同时,忽略标识符后,按内容字母顺序排序:在内容

  • php数组函数序列之next() - 移动数组内部指针到下一个元素的位置,并返回该元素值

    next() 定义和用法 next() 函数把指向当前元素的指针移动到下一个元素的位置,并返回该元素的值. 如果内部指针已经超过数组的最后一个元素,函数返回 false. 语法 next(array)参数 描述 array 必需.规定要使用的数组. 说明 next() 和 current() 的行为类似,只有一点区别,在返回值之前将内部指针向前移动一位.这意味着它返回的是下一个数组单元的值并将数组指针向前移动了一位.如果移动指针的结果超出了数组单元的末端,则 next() 返回 FALSE. 注

  • 按下回车键指向下一个位置的一个函数代码

    复制代码 代码如下: function tofocus(itemname)    //按回车置下一个位置         {             var a             a=eval("document.vouch."+itemname)             a.focus()         } 在控件中使用onkeypress="javascrip:if(window.event.keyCode==13){tofocus('nextformname')

  • js和jquery中循环的退出和继续下一个循环

    作为水货,就是学会了1+1=3也要记录一下!错了,是2 学习记录: js中的 for(var i=1;i<5;i++){ if(i==3){ break; // 使用break,弹出2次提示分别为1,2:如果使用continue,则会弹出3次,分别是1,2,4 } alert(i); } 循环,退出循环,使用break:退出当前循环继续下一个循环,使用continue jquery中的each()方法中要实现break,使用return false:continue,使用return true

  • js jquery获取当前元素的兄弟级 上一个 下一个元素

    var chils= s.childNodes;  //得到s的全部子节点 var par=s.parentNode;   //得到s的父节点 var ns=s.nextSbiling;   //获得s的下一个兄弟节点 var ps=s.previousSbiling;  //得到s的上一个兄弟节点 var fc=s.firstChild;   //获得s的第一个子节点 var lc=s.lastChile;   //获得s的最后一个子节点 JS获取节点父级,子级元素 先说一下JS的获取方法,其

  • JQuery 文本框回车跳到下一个文本框示例代码

    复制代码 代码如下: loginInputForm.find('input').on('keyup',function(){ if(event.keyCode=='13'){ 执行跳到下一个文本框的代码 } });

  • javascript获取dom的下一个节点方法

    javascript获取dom的下一个节点方法

    利用javascript 写一个在页面点击加减按钮实现数字的累加. 简略的html大概如此.看得懂就好不要在意这些细节啊 <input type="button" value="+" onclick="jia(this)" /> <label class="num">0</label> <input type="button" value="-"

随机推荐