Next Permutation--LeetCode

淩亂°似流年 2022-08-07 13:41 173阅读 0赞

mplement 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, do not allocate 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`

使用STL中的思路，从后往前找一对相邻的数，在一对相邻的数中第一个元素小于第二个元素，记做\*i<\*ii，从后往前找到第一个元素\*j，是的\*j>\*i，然后交换\*i和\*j，然后交换从\*II开始（包含\*ii在内）到数组末尾的序列。

void Rserve(vector<int>& vec,int begin,int end)  
    {  
        while(begin <= end)  
        {  
            swap(vec[begin],vec[end]);  
            begin++;  
            end--;  
        }  
    }   
      
    bool FindPair(vector<int>& vec,int& first,int& second)  
    {  
        int last = vec.size()-1;  
        for(;last>0;last--)  
        {  
            second = last;  
            first = last-1;  
            if(vec[first] < vec[second])  
                return true;  
        }  
        return false;  
    }  
      
    void nextPermutation(vector<int>& vec)  
    {  
        int first,second,index;  
        if(FindPair(vec,first,second))  
        {  
            index = vec.size()-1;  
            for(;index>=first;index--)  
            {  
                if(vec[index] > vec[first])  
                    break;  
            }  
            swap(vec[index],vec[first]);  
            Rserve(vec,second,vec.size()-1);   
        }  
    }

``

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关链表P-＞NEXT=Q-＞NEXT,Q-＞NEXT=P,Q=P；的一些解释

假设刚开始p指向t，q指向了b。如下图所示 ![1d1d25284d72b9dbb87df0c736c949b1.png][] 首先p->next=q->next: 意

心已赠人/ 2023年10月11日 19:33/ 0 赞/ 35 阅读

相关 q-＞next=p-＞next；

对于链表的学习，开始的时候对q->next=p->next;这个语句是理解的，后来学着学着就糊涂了，所以就用了一张图来帮助自己理解 ![在这里插入图片描述][watermar

拼搏现实的明天。/ 2023年02月28日 05:37/ 0 赞/ 13 阅读

相关 KMP算法next数组中k = next[k]

KMP算法next数组中k = next\[k\] next数组是KMP算法的关键，用于储存模式串指针j回溯的值，当模式串与主串失配时，利用next数组更快地找到模式串下

「爱情、让人受尽委屈。」/ 2023年02月10日 12:28/ 0 赞/ 19 阅读

相关 java的next()_Java Scanner next()方法

Java Scanner next()方法 java.util.Scanner.next(String pattern) 方法返回下一个标记，如果它匹配从指定字符串构造的模式

水深无声/ 2022年11月06日 10:47/ 0 赞/ 204 阅读

相关 Next Permutation--LeetCode

mplement next permutation, which rearranges numbers into the lexicographically next grea

淩亂°似流年/ 2022年08月07日 13:41/ 0 赞/ 174 阅读

相关 HTML中 start next prev 属性值

原文：[http://www.dreamdu.com/xhtml/attribute\_start\_next\_prev/][http_www.dreamdu.com_xht

向右看齐/ 2022年08月06日 13:23/ 0 赞/ 161 阅读

相关 next数组介绍

首先看看next数组值的求解方法例如：模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2

比眉伴天荒/ 2022年08月05日 10:27/ 0 赞/ 171 阅读

相关 Next Permutation

题目 Implement next permutation, which rearranges numbers into the lexicographically ne

左手的ㄟ右手/ 2022年06月06日 04:42/ 0 赞/ 175 阅读

相关 while (rs.next()) 与 if(rs.next())的区别

如果说是"判断结果集里有没有值" 那么用if(rs.next) while是用来做循环输出的换句话说就是"如果结果集里还有值" 没有则停止循环这个一般在JSP

柔情只为你懂/ 2022年05月26日 10:24/ 0 赞/ 164 阅读

相关 next.js 初试

-------------------- title: next.js入门 tag：next.js, react 序章服务端渲染服务端渲染（S

淩亂°似流年/ 2022年01月12日 03:23/ 0 赞/ 273 阅读