内容简介:题目描述:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
题目描述:
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解答:
直接给出步骤:
1从右到左扫描数组找出第一个升序对(nums[j-1],nums[j])
2从右到左扫描数组找出第一个大于nums[j-1]的数nums[k]
3交换nums[j-1],nums[k]
4对num[j...nums.length-1]转置。
java ac代码:
class Solution {
public void nextPermutation(int[] nums) {
boolean flag = true;
int i = 0;
for(;i < nums.length-1;i++)
if(nums[i] < nums[i+1])
{
flag = false;
break;
}
if(flag)
{
int x = 0,y = nums.length-1;
while(x < y)
{
swap(nums,x,y);
x++;
y--;
}
}
else
{
i = nums.length-1;
while(i >= 1)
if(nums[i] <= nums[i-1])i--;
else break;
int j = nums.length-1;
for(;j >= 0;j--)
if(nums[j] > nums[i-1])break;
swap(nums,i-1,j);
int x = i,y = nums.length-1;
while(x < y)
{
swap(nums,x,y);
x++;
y--;
}
}
}
void swap(int[] nums,int x,int y)
{
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
计算机科学概论(第12版)
[美] J.Glenn Brookshear、[美] Dennis Brylow / 刘艺、吴英、毛倩倩 / 人民邮电出版社 / 2017-1 / 69.00
《计算机科学概论》是计算机科学概论课程的经典教材,全书对计算机科学做了百科全书式的精彩阐述,充分展现了计算机科学的历史背景、发展历程和新的技术趋势。《计算机科学概论》首先介绍的是信息编码及计算机体系结构的基本原理,进而讲述操作系统和组网及因特网,接着探讨算法、程序设计语言及软件工程,然后讨论数据抽象和数据库方面的问题,讲述图形学的一些主要应用以及人工智能,以计算理论的介绍结束全书。《计算机科学概论......一起来看看 《计算机科学概论(第12版)》 这本书的介绍吧!