Binary search based solution


  • 0
    X
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int start = 0;
        if (n <= 1) {
            return;
        }
        
        for (int i = n - 1; i > 0; i --) {
            if (nums[i] > nums[i-1]) {
                int index = binary_search_greater(nums, i, n-1, nums[i-1]);
                int tmp = nums[i-1];
                nums[i-1] = nums[index];
                nums[index] = tmp;
                
                start = i;
                break;
            } 
        }
        
        reverse_array_tail(nums, start);
        
        return;
    }
    
    int binary_search_greater(vector<int>& nums, int start, int end, int val) {
        int mid;
        
        while(start + 1 < end) {
            mid = start + (end - start)*0.5;
            
            if (nums[mid] <= val) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        return (nums[end] > val)? end : start;
    }
    
    void reverse_array_tail(vector<int>& nums, int start) {
        int end = nums.size() - 1;
        while(start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            
            start ++;
            end --;
        }
        
        return;
    }
    

    };


Log in to reply
 

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