LeetCode 31题:下一个排列

这篇具有很好参考价值的文章主要介绍了LeetCode 31题:下一个排列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目

思路

代码


题目

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

  • 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3][1,3,2][3,1,2][2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

  • 例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ,找出 nums 的下一个排列。

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

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]

示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]

示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

思路

一串数字排列的下一个排序找法是:从末尾开始找第一次出现nums[ i ] >nums[ i-1 ] 的位置,在 i -1之前的数字排序不变,在 i -1之后寻找大于nums[ i-1 ]的最小值,找到后与nums[ i-1 ]交换。交换后,i - 1之后的数字按非递减排序即可。

LeetCode 31题:下一个排列,LeetCode练习题,leetcode,算法,数据结构,c语言


代码

#include<stdio.h>
#include<stdlib.h>

void nextPermutation(int* nums, int numsSize);

int main()
{
    int nums[3]={1};
    int size=1;
    nextPermutation(nums,size);
    for(int i=0;i<size;i++)
    {
        printf("%d ",nums[i]);
    }
    return 0;
}

void nextPermutation(int* nums, int numsSize)
{
    int sign=0;
    int i;
    for(i=numsSize-1;i>0&&nums[i]<=nums[i-1];i--);
    if(numsSize==1)
    return ;
    if(i==0&&nums[i+1]<=nums[i])
    {
        int left=0,right=numsSize-1;
        while(left<right)
        {
            int x=nums[left];
            nums[left]=nums[right];
            nums[right]=x;
            left++;
            right--;
        }
    }
    else
    {
        int target=i;
        int min=nums[i];
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[j]>nums[i-1]&&nums[j]<min)
            {
                min=nums[j];
                target=j;
            }
        }
        int a=nums[target];
        nums[target]=nums[i-1];
        nums[i-1]=a;
        int len=numsSize-i;
        for(int p=len/2;p>=1;p=p/2)
        {
            for(int q=i+p;q<numsSize;q++)
            {
                int temp=nums[q];
                int j;
                for(j=q-p;j>=i&&nums[j]>temp;j=j-p)
                {
                    nums[j+p]=nums[j];
                }
                nums[j]=temp;
            }
        }
    }
}

LeetCode 31题:下一个排列,LeetCode练习题,leetcode,算法,数据结构,c语言 

 文章来源地址https://www.toymoban.com/news/detail-647188.html

到了这里,关于LeetCode 31题:下一个排列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】练习习题集【4月 - 7 月】

    1.重复数 题目: 代码: 9.回文数 题目: 思路: 如果是负数一定不是回文数 直接返回false 如果是正数,则将其倒序数值计算出来,然后比较和原数值是否相等 如果是回文数相等返回true 不相等返回false 代码: 13. 罗马数字转整数 (https://leetcode.cn/problems/roman-to-integer/) 题目:

    2024年02月13日
    浏览(43)
  • 【数据结构】顺序表详解(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺

    2023年04月27日
    浏览(49)
  • Golang | Leetcode Golang题解之第31题下一个排列

    题目: 题解:

    2024年04月17日
    浏览(43)
  • 模拟实现atoi函数(将数字字符串转换为整型)附加leetcode练习题

    各位朋友们,大家好啊!今天我为大家分享的知识是如何模拟实现atoi函数。相信大家如果能够理解这个知识,对大家以后的刷题是有帮助的。 我们要想实现某个函数,我们肯定要先知道这个函数的作用是什么,然后我们再根据它的作用来自己实现。我们先来看看stoi函数在库

    2023年04月19日
    浏览(58)
  • 练习题----顺序栈算法

    ​输入一个包括 \\\'(\\\' 和 \\\')\\\' 的字符串string ,判断字符串是否有效。要求设计算法实现检查字符串是否有效,有效的字符串需满足以下条件: A. 左括号必须用相同类型的右括号闭合。 B. 左括号必须以正确的顺序闭合。 C. 每个右括号都有一个对应的相同类型的左括号。 ​该题需

    2024年04月26日
    浏览(42)
  • <算法学习>动态规划练习题

    本篇文章为初学动态规划时的练习题。参考优质博客学习后根据伪代码描述完成代码。记录一下用于以后复习。 给定一个有n行数字组成的数字三角形. 试设计一个算法, 计算出从三角形的顶至底的一条路径, 使该路径经过的数字和最大. 算法设计: 对于给定的n行数字组成的三角

    2024年01月17日
    浏览(48)
  • Matlab:遗传算法,模拟退火算法练习题

    1、遗传算法 (1) 遗传算法 是一种基于自然选择原理和自然遗传机 制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目 标的优化。遗传算法的实质是通过群体搜索技术,根据适者生存的原则逐代进化,最终 得到最优解或准最优解。它必须

    2024年01月21日
    浏览(47)
  • 拓扑排序 (算法思想+图解+模板+练习题)

    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。 无向图没有拓扑序列。 首先我们先来解释一下什么是有向无环图: 有向就是我们两个结点之间的边是有方向的,无环的意思就是整个序列中没有几个结点通过边形成一个圆环。 下图就是一个有向无环图,它也一定

    2024年02月03日
    浏览(70)
  • 【算法设计与分析】动态规划-练习题

    输入一个整数数组 S[n] ,计算其最长递增子序列的长度,及其最长递增子序列。 定义 k ( 1 ≤ k ≤ n ) k (1 ≤ k ≤ n) k ( 1 ≤ k ≤ n ) ,L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。 对于每一个k,我们都遍历前面0~k-1的所有的数,找出最大的L[i],且 S [ k ] L [

    2024年02月03日
    浏览(58)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包