lt- 31.下一个排列
[案例需求]
[思路分析]
- 本题解法相当朴素, 没有辣么多花里胡哨的东西;
- 题目要求我们求出一个比当前序列稍微大一点的数, 如果本序列是递减的序列, 那已经是这个序列能够组合出来的最大数了, 题目要求我们把这个序列重排为字典序最小的序列, 直接对整个序列翻转即可;
- 那么对于存在下一个排列的情况, 应该如何求呢?
- 题目的关键点就在于
找到一个非递减顺序的关键点, 比如3421的下一个较大的排列就是在3处找到的, 3在这个序列中非递减的,
所以整体的解题思路就是:
-
先倒序遍历数组, 找到第一个 (前一个数比后一个数小的位置) (即nums[i] < nums[i+1]);
-
这个时候我们不能直接把后一个数nums[i+1] 跟前一个数nums[i]交换就完事了; 还应该从nums[i+1]–>数组末尾这一段的数据中 找出最优的那个值( 如何最优? 即比nums[i]稍微大那么一丢丢的数, 也就是 nums[i+1]–>数组末尾中, 比nums[i]大的数中最小的那个值)
-
找到之后, 跟num[i]交换, 这还不算是下一个排列, num[i]后面的数值还不够小, 所以还应当进升序排列
举个栗子:
nums = [1,2,7,4,3,1],
-
倒序遍历数组, 找出第一组: 前一个数比后一个数小的两个数, 即[2, 7]
-
所处的这个位置就是需要找出比它稍微大的数的位置;
-
我们从[7,4,3,1]中找出比2大的数中的最小值, 也就是3, 找到后跟2交换即可;; 当然了, 如果没找到的话, 直接跳到第5步, 直接升序排列输出.
-
目前nums=[1,3,7,4,2,1], 不用我说你们也看出来还不算下一个排列
-
对3后面的数, 升序排列, 即最终结果: nums = [1,3,1,2,4,7]
[代码实现一, 学弱解法, 需要优化]
// 1. 削弱解法
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
//倒序遍历. 找出升序的第一个数
int firstMin = -1;
for(int i = len - 2; i >= 0; i--){
if(nums[i] < nums[i + 1]){
firstMin = i;
break;
}
}
if(firstMin == -1){
reverse(nums, 0, len - 1);
return;
}
System.out.println("" + firstMin);
//在i + 1 ~ len范围内, 找出大于nums[i]的最小数
int firstMinNum = nums[firstMin];
int minMax = Integer.MAX_VALUE;
int targetIndex = 0;
for(int i = firstMin + 1; i < len; i++){
if(nums[i] > firstMinNum){
minMax = Math.min(minMax, nums[i]);
if(minMax == nums[i]){
targetIndex = i;
}
}
}
//交换
swap(nums, targetIndex, firstMin);
System.out.println("" + firstMin );
//然后对firstMin后面的序列进行局部排序(升序排咧)
//直接反转
reverse(nums, firstMin + 1, len - 1);
}
public void swap(int[] nums,int left, int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void reverse(int[] nums, int begin, int end){
while(begin < end){
swap(nums, begin++, end--);
}
}
}
[代码实现2, ]
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 倒序遍历, 找出第一个升序的数,
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
//经过上面的遍历, 如1,2,7,4,3,1 i此时为1 即 nums[i] = nums[1] = 2
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--; //找到 i后面的序列中比nums[i]大的第一个数
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
lt- 556. 下一个更大元素 III
[案例需求]
[思路分析]
- 就是上一题的翻版
- 这里只不过是要掌握以下知识点:
1. 数字->String->char[] 三者的互相转换
2. 数字->String: String.valueOf(number) 或 new String(number);
3. String -> char[] : str.toCharArray()
4. char[] --> String: new String(char数组) 或 String.valueOf(char数组)
5. String --> 数字: Integer.parseInt(str)
6. char --> 数字: ch - ‘0’
注意由于char字符可以用来表示acsii值, 所以也可以直接当做数字比较大小
[代码实现]
//1. 学弱解法
class Solution {
public int nextGreaterElement(int n) {
/**
倒序遍历, 找到非递减的第一个数 i
再次倒序i到末尾的序列, 找到第一个比他大的数
交换
*/
String numStr = String.valueOf(n);
char[] numChars = numStr.toCharArray();
int i = numChars.length - 2;
while(i >= 0 && numChars[i + 1] <= numChars[i]){
--i;
}
if(i < 0)return -1;
if(i >= 0){
int j = numChars.length - 1;
while(j >= 0 && numChars[i] >= numChars[j]){
--j;
}
swap(numChars, i, j);
}
if(i >= 0)reverse(numChars, i + 1);
//return i < 0 ? -1 : Integer.parseInt(new String(numChars));\
long res = 0;
for(char c : numChars){
res = res * 10 + c - '0';
}
return res > Integer.MAX_VALUE ? -1 : (int)res;
}
public void swap(char[] nums, int left, int right){
char temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public void reverse(char[] nums, int j){
int end = nums.length - 1;
while(j < end){
swap(nums, j++, end--);
}
}
}
