Simple C++ solution with explanation


  • 0
    M

    Basic idea is to traverse from back and find the first index which has any number bigger than that index on right.
    Once you get that index, simply swap the biggest number you had found with that index, and sort the right side of array from that index.

    '''
    bool has_bigger(vector <int>&nums, int idx) {
    for (int i = idx; i < nums.size(); i++) {
    if (nums[i] > nums[idx]) return true;
    }
    return false;
    }

    int get_bigger(vector <int>&nums, int idx) {
        int val = nums[idx];
        int x, maxv = INT_MAX;
        for (int i = idx; i < nums.size(); i++) {
            if (nums[i] > val && nums[i] < maxv) {
                maxv = nums[i];
                x = i;
            }
        }
        
        return x;
    }
    
    void nextPermutation(vector<int>& nums) {
        int l = nums.size() - 1;
        for (int i = l - 1; i >= 0; i--) {
           if (has_bigger(nums, i)) {
               int x = get_bigger(nums, i);
               swap(nums[x], nums[i]);
               sort(nums.begin() + i + 1, nums.end());
               return;
           }   
        }
        
        sort(nums.begin(), nums.end());
    }
    

    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.