Bài 31 Leetcode: Next Permutation

Đề bài:

Một hoán vị của một mảng số nguyên là một sắp xếp các thành viên của nó thành một chuỗi hoặc thứ tự tuyến tính.

  • Ví dụ, với arr = [1,2,3], dưới đây là tất cả các hoán vị của arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

Hoán vị kế tiếp của một mảng số nguyên là hoán vị kế tiếp lớn hơn trong thứ tự từ điển của số nguyên đó. Cụ thể hơn, nếu tất cả các hoán vị của mảng được sắp xếp trong một container theo thứ tự từ điển của chúng, thì hoán vị kế tiếp của mảng đó là hoán vị tiếp theo trong container đã sắp xếp. Nếu sắp xếp như vậy không khả thi, mảng phải được sắp xếp lại theo thứ tự thấp nhất có thể (tức là sắp xếp tăng dần).

  • Ví dụ, hoán vị kế tiếp của arr = [1,2,3] là [1,3,2].
  • Tương tự, hoán vị kế tiếp của arr = [2,3,1] là [3,1,2].
  • Trong khi hoán vị kế tiếp của arr = [3,2,1] là [1,2,3] vì [3,2,1] không có một sắp xếp lại lớn hơn theo thứ tự từ điển.

Cho một mảng số nguyên nums, tìm hoán vị kế tiếp của nums.

Việc thay thế phải được thực hiện tại chỗ và chỉ sử dụng bộ nhớ phụ hằng số.

Ví dụ 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Ví dụ 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Ví dụ 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Ràng buộc:

  • 1 <= độ dài của nums <= 100
  • 0 <= nums[i] <= 100

Giải thích thuật toán bằng C++

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    const int n = nums.size();

    // From back to front, find the first number < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From back to front, find the first number > nums[i], swap it with
    // nums[i].
    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums[i], nums[j]);
          break;
        }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
  }

 private:
  void reverse(vector<int>& nums, int l, int r) {
    while (l < r)
      swap(nums[l++], nums[r--]);
  }
};

Đoạn mã trên triển khai thuật toán để tạo ra hoán vị kế tiếp của một mảng số nguyên.

Thuật toán này hoạt động như sau:

1. Tính kích thước `n` của mảng `nums`.

2. Tìm vị trí `i` sao cho `nums[i] < nums[i + 1]` từ phải qua trái. Ý nghĩa của bước này là tìm điểm dừng để thực hiện các bước tiếp theo để tạo ra hoán vị kế tiếp. Nếu không tìm thấy `i`, tức là mảng đã được sắp xếp giảm dần, ta đảo ngược toàn bộ mảng để tạo hoán vị đầu tiên và kết thúc thuật toán.

3. Từ phải qua trái, tìm phần tử đầu tiên lớn hơn `nums[i]` và ghi nhận vị trí `j`. Sau đó, hoán đổi `nums[i]` với `nums[j]`.

4. Đảo ngược phần còn lại của mảng `nums` từ `i + 1` tới `n – 1`. Điều này sẽ đảo ngược thứ tự của các phần tử từ vị trí `i + 1` đến cuối mảng, tạo ra hoán vị kế tiếp.

Ví dụ, nếu mảng ban đầu là `[1, 2, 3]`, sau khi áp dụng thuật toán, mảng sẽ trở thành `[1, 3, 2]`, là hoán vị kế tiếp của mảng ban đầu.

Giải thích thuật toán bằng Java

class Solution {
  public void nextPermutation(int[] nums) {
    final int n = nums.length;

    // From back to front, find the first number < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From back to front, find the first number > nums[i], swap it with
    // nums[i].
    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums, i, j);
          break;
        }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
  }

  private void reverse(int[] nums, int l, int r) {
    while (l < r)
      swap(nums, l++, r--);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def nextPermutation(self, nums: List[int]) -> None:
    n = len(nums)

    # From back to front, find the first number < nums[i + 1].
    i = n - 2
    while i >= 0:
      if nums[i] < nums[i + 1]:
        break
      i -= 1

    # From back to front, find the first number > nums[i], swap it with nums[i].
    if i >= 0:
      for j in range(n - 1, i, -1):
        if nums[j] > nums[i]:
          nums[i], nums[j] = nums[j], nums[i]
          break

    def reverse(nums: List[int], l: int, r: int) -> None:
      while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

    # Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, len(nums) - 1)

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.