Hướng dẫn next permutation leetcode solution c++ - giải pháp leetcode hoán vị tiếp theo c ++

(LeetCode: Trung bình)

Thực hiện hoán vị tiếp theo, sắp xếp lại số vào từ vựng tiếp theo về mặt từ vựng tiếp theo của các số.next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Nếu một sự sắp xếp như vậy là không thể, nó phải sắp xếp lại nó là thứ tự thấp nhất có thể (tức là, được sắp xếp theo thứ tự tăng dần).

Việc thay thế phải được đặt tại chỗ và chỉ sử dụng bộ nhớ thêm không đổi.in place and use only constant extra memory.

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]

Ví dụ 4:

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

Constraints:

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

  4

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

  5

class Solution {
public:
    void nextPermutation(vector& nums) {
        int n = nums.size(), k, l;
        for(k = n-2 ; k>=0 ; k--){
            if(nums[k]                break;
            }
        }
        if(k<0){
            reverse(nums.begin(), nums.end());
        }else{
            for(l = n-1 ; l>k ; l--){
                if(nums[l] > nums[k]){
                    break;
                }
            }
            swap(nums[k], nums[l]);
            reverse(nums.begin()+k+1, nums.end());
        }
    }
};To get the intution behind the logic let us first dry run a input and see how it works :nums = [1,2,3]
n = 3 ,  k = 1
nums[1] = 2 and nums[2] = 3 , 2 < 3
so now it exits k = 1 and 1 > 0 
l = 2 
nums[1] = 2 and nums[2] = 3
so nums[l] < nums[k] 
so swap them , nums = [1,3,2]
Now reverse(nums.begin()+1+1,nums.end())
nums = [1,3,2] which is the required answer. 

Các intutuion cơ bản đằng sau logic này được đưa ra dưới đây. Tôi tìm thấy điều này trên LeetCode và nó đưa ra một lời giải thích chính xác sạch sẽ. Tôi đây đang đính kèm một số tài nguyên khác cho sự hiểu biết và rõ ràng hơn của bạn.

1. https://leetcode.com/problems/next-permutation/discuss/1448059/C%2B%2B-or-Solution-with-explanation-or-Easy-for-beginners
2. https://leetcode.com/problems/next-permutation/
3. https://www.youtube.com/watch?v=LuLCLgMElus&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=11
4. https://docs.google.com/document/d/1SM92efk8oDl8nyVw8NHPnbGexTS9W-1gmTEYfEurLWQ/edit

Cho đến khi tiếp tục mã hóa và tiếp tục học hỏi! Hãy theo dõi để biết thêm

Vì bạn rất thích đọc blog của tôi, tại sao không mua cho tôi một ly cà phê và suboort công việc của tôi ở đây !! https://www.buymeacoffee.com/sukanyabharati

Đảo ngược các mảng con bắt đầu từ str [i] ..

• Xin chào các nhà phát triển 👋! Nó đã được một thời gian dài kể từ khi tôi viết một bài viết về các vấn đề về LeetCode. Nhưng không phải lo lắng, hôm nay sẽ thảo luận về vấn đề tiếp theo.

Hoán vị tiếp theo

Báo cáo vấn đề

Thực hiện hoán vị tiếp theo, sắp xếp lại số vào từ vựng tiếp theo về mặt từ vựng tiếp theo của các số.

Nếu một sự sắp xếp như vậy là không thể, nó phải sắp xếp lại nó là thứ tự thấp nhất có thể (tức là, được sắp xếp theo thứ tự tăng dần).

Constraints:

• Việc thay thế phải được đặt tại chỗ và chỉ sử dụng bộ nhớ thêm không đổi.
• 1 ≤

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

  6 ≤ 100

0 ≤ Input: nums = [3,2,1]Output: [1,2,3]7 ≤ 100

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]

Ví dụ 4:

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

Phân tích

Vấn đề là thẳng về phía trước. Chúng tôi sẽ được cung cấp một loạt các số nguyên và chúng tôi cần tìm sự hoán vị tiếp theo có thể của số được hình thành bằng cách kết hợp các phần tử của mảng.

Ví dụ: nếu mảng được đưa ra là

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

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

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

Các ràng buộc là chúng ta cần thực hiện điều này mà không cần thêm không gian và sửa đổi chỉ được thực hiện tại chỗ.without extra space and modifications are done only in-place.

Cách tiếp cận

Chúng ta có thể làm theo các bước dưới đây -

1. Quét mảng từ phải sang trái cho đến khi tìm thấy một phần tử nhỏ hơn chỉ mục ở bên phải. Đánh dấu chỉ số của phần tử như

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

   0.
2. Một lần nữa quét mảng từ phải sang trái cho đến khi tìm thấy một phần tử lớn hơn phần tử được tìm thấy trong bước trên. Đánh dấu chỉ số của các yếu tố như

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

   1.
3. Trao đổi hai yếu tố tại các chỉ số

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

   0 và

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

   1.
4. Bây giờ, đảo ngược mảng từ Index

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

   0 cho đến khi kết thúc mảng.

Hãy để hiểu điều này với một ví dụ -

nums = [4,5,3,2,1]

Step 1: scan from right to left and stop at 4 because it less than 5. Here, index = 0
Step 2: Again scan from right to left and stop at 5 because it is greater than 4. Here, j = 1
Step 3: Swap the elements at index and j. The array will become [5,4,3,2,1].
Step 4: Reverse the array after index. The array will become [5,1,2,3,4]

Độ phức tạp về thời gian

Chúng tôi đang lặp lại mảng hai lần. Trong trường hợp xấu nhất, độ phức tạp về thời gian sẽ là O (2N) tương đương với O (n).O(2n) which is equivalent to O(n).

Độ phức tạp không gian

Chúng tôi không sử dụng bất kỳ cấu trúc dữ liệu nào cho các tính toán trung gian. Do đó, độ phức tạp không gian sẽ là O (1).O(1).

Mã số

Java

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

Python

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

JavaScript

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

Kotlin

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

Hoàn thành mã

• Java
• Python
• JavaScript
• Kotlin

Hoàn thành mã

Sự kết luận

Xin chúc mừng! Hôm nay chúng tôi đã giải quyết một vấn đề khá đơn giản để xác định hoán vị tiếp theo của số.

Tôi hy vọng bạn thích bài viết này. Hãy chia sẻ suy nghĩ của bạn về điều này.

Bạn có thể tìm thấy mã nguồn đầy đủ trên kho lưu trữ GitHub của tôi. Nếu bạn thích những gì bạn học, hãy thoải mái và sao.

Hoán vị tiếp theo trong c là gì?

Làm thế nào để bạn tìm thấy hoán vị tiếp theo của một số?