31. Next Permutation
Tags:
Medium
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tìm hoán vị tiếp theo lớn hơn của một dãy số nguyên theo thứ tự từ điển. Nếu không tồn tại hoán vị lớn hơn, bạn cần trả về hoán vị nhỏ nhất (sắp xếp lại dãy theo thứ tự tăng dần)
Hoán vị lớn hơn của một dãy số là cách sắp xếp tiếp theo trong thứ tự từ điển (lexicographical order). Thứ tự này giống như cách bạn sắp xếp các từ trong từ điển: Từ nhỏ nhất đến lớn nhất
Example:
Cho dãy số [1][2][3], các hoán vị theo thứ tự từ điển là:
[1,[2][3][1,[3][2][2,[1][3][2,[3][1][3,[1][2][3,[2][1]Nếu bạn đang ở hoán vị [1][2][3], thì hoán vị lớn hơn tiếp theo là [1][3][2]. Nếu bạn đang ở hoán vị cuối cùng [3][2][1], thì không có hoán vị lớn hơn nữa — bạn phải quay lại hoán vị nhỏ nhất là [1,[2][3].
Bước 1: Tìm điểm “đảo ngược”
Bước 2: Tìm phần tử lớn hơn tại bên phải điểm đảo ngược
Bước 3: Hoán đổi và đảo ngược
Approach
Bước 1: Tìm điểm “đảo ngược” (pivot)
Bước 2: Xác định phần tử kế tiếp lớn hơn pivot
Bước 3: Hoán đổi pivot và phần tử kế tiếp
Bước 4: Đảo ngược phần tử sau pivot
Solution
1function nextPermutation(nums: number[]): void {
2 const n = nums.length;
3 let i = n - 2;
4
5 while (i >= 0 && nums[i] >= nums[i + 1]) {
6 i--;
7 }
8
9 if (i >= 0) {
10 for (let j = n - 1; j > i; j--) {
11 if (nums[j] > nums[i]) {
12 [nums[i], nums[j]] = [nums[j], nums[i]]
13 break
14 }
15 }
16 }
17
18 let start = i + 1;
19 let end = n - 1;
20 while (start < end) {
21 [nums[start], nums[end]] = [nums[end], nums[start]]
22 start++;
23 end--;
24 }
25}