当前位置:网站首页>LeetCode 31. Next spread
LeetCode 31. Next spread
2022-07-05 09:26:00 【Sasakihaise_】
【 analysis 】 If you want to get an element larger than the current number , We need to exchange the next larger number with the previous smaller number , And the bits exchanged in front should be as low as possible , The numbers exchanged later should be as small as possible , But it has to be bigger than the front . Then it needs to be done in two steps :
1. Find the position of the previous element to be exchanged .
2. Look for the smallest element larger than him from the back .
about 1, Let's look at a situation 5,4,3,2,1, We find that this number is already the largest arrangement , That is, you can't find the position you can exchange in front . But for permutations 3,5,4,2,1, If you cover up 3, hinder 5,4,2,1 It is already the maximum , however 3 This position can be changed , So it is not difficult to find , When a sequence is arranged in reverse order , His composition is already the maximum . If such two elements are found (i, j),nums[i] < nums[j], Explain that you can change nums[i] To make the element bigger . In this way, we find the minimum bit of the element to be exchanged .
about 2, Suppose the insertion position is i, that [i + 1, n) It must be in descending order , Continue traversing from back to front , Just look for the first element larger than the insertion position , This element is greater than i The smallest element of the element at .
After exchange , because [i + 1, n) Or in descending order , He is still a big number , But because of the exchange i Cause of , No matter how they are arranged in the back , Are bigger than the previous one , In order to make the result smaller , Also change this part into ascending order .( You can directly reverse , It's fine too sort)
class Solution {
// Monotonic stack 10:12 10:30
// Looking back and forth , If it's in ascending order , The description cannot be changed later, for example 4 6 5 3 2 1, We cannot change 65321 From your location
// Find the next one
// however 4 6 It's in reverse order , Explain that you can find a comparison in the back 4 Large element exchange to make the exchange larger than before
// The first ratio found from the back 4 The big one is 5, In exchange for 4 and 5 And then get 5 6 4 3 2 1, But now it's not the smallest element
// It can only be said that 5 The element at the beginning must be larger than that just now 4 At the beginning , So we have to deal with 5 The following elements are arranged in order from small to large
// current 5 1 2 3 4 6 Is the next smallest element
public void nextPermutation(int[] nums) {
int n = nums.length, i, j;
for (i = n - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
break;
}
}
if (i == -1) {
Arrays.sort(nums);
return;
}
for (j = n - 1; j > i; j--) {
if (nums[j] > nums[i]) {
break;
}
}
var t = nums[i];
nums[i] = nums[j];
nums[j] = t;
Arrays.sort(nums, i + 1, n);
}
}
class Solution {
// Monotonic stack 10:12 10:30
// Looking back and forth , If it's in ascending order , The description cannot be changed later, for example 4 6 5 3 2 1, We cannot change 65321 From your location
// Find the next one
// however 4 6 It's in reverse order , Explain that you can find a comparison in the back 4 Large element exchange to make the exchange larger than before
// The first ratio found from the back 4 The big one is 5, In exchange for 4 and 5 And then get 5 6 4 3 2 1, But now it's not the smallest element
// It can only be said that 5 The element at the beginning must be larger than that just now 4 At the beginning , So we have to deal with 5 The following elements are arranged in order from small to large
// current 5 1 2 3 4 6 Is the next smallest element
public void nextPermutation(int[] nums) {
int n = nums.length, i, j;
for (i = n - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
break;
}
}
if (i == -1) {
i = 0; j = n - 1;
while (i < j) {
int t = nums[i];
nums[i++] = nums[j];
nums[j--] = t;
}
return;
}
for (j = n - 1; j > i; j--) {
if (nums[j] > nums[i]) {
break;
}
}
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
i++;
j = n - 1;
while (i < j) {
t = nums[i];
nums[i++] = nums[j];
nums[j--] = t;
}
}
}
边栏推荐
- Rebuild my 3D world [open source] [serialization-3] [comparison between colmap and openmvg]
- 迁移学习和域自适应
- Talking about the difference between unittest and pytest
- Jenkins pipeline method (function) definition and call
- Nips2021 | new SOTA for node classification beyond graphcl, gnn+ comparative learning
- C # draw Bezier curve with control points for lattice images and vector graphics
- Shutter uses overlay to realize global pop-up
- Kotlin introductory notes (IV) circular statements (simple explanation of while, for)
- NIPS2021 | 超越GraphCL,GNN+对比学习的节点分类新SOTA
- [code practice] [stereo matching series] Classic ad census: (6) multi step parallax optimization
猜你喜欢
OpenGL - Model Loading
LeetCode 503. 下一个更大元素 II
Unity skframework framework (XXII), runtime console runtime debugging tool
High performance spark_ Transformation performance
利用请求头开发多端应用
Attention is all you need
Hi Fun Summer, play SQL planner with starrocks!
Blogger article navigation (classified, real-time update, permanent top)
Kotlin introductory notes (VIII) collection and traversal
顶会论文看图对比学习(GNN+CL)研究趋势
随机推荐
Android 隐私沙盒开发者预览版 3: 隐私安全和个性化体验全都要
Information and entropy, all you want to know is here
Talking about label smoothing technology
It's too difficult to use. Long articles plus pictures and texts will only be written in short articles in the future
Understanding rotation matrix R from the perspective of base transformation
3D reconstruction open source code summary [keep updated]
[beauty of algebra] solution method of linear equations ax=0
我的一生.
【阅读笔记】图对比学习 GNN+CL
阿里十年测试带你走进APP测试的世界
What is a firewall? Explanation of basic knowledge of firewall
2311. Longest binary subsequence less than or equal to K
【PyTorch Bug】RuntimeError: Boolean value of Tensor with more than one value is ambiguous
c语言指针深入理解
微信小程序获取住户地区信息
[beauty of algebra] singular value decomposition (SVD) and its application to linear least squares solution ax=b
高性能Spark_transformation性能
Rebuild my 3D world [open source] [serialization-3] [comparison between colmap and openmvg]
L'information et l'entropie, tout ce que vous voulez savoir est ici.
The research trend of map based comparative learning (gnn+cl) in the top paper