Share my 2ms java solution


  • 0
    J

    public class Solution {
    public void nextPermutation(int[] nums) {

    	if(nums.length < 2) 
    		return;
    	int i, j, temp;
        for(i = nums.length - 2; i >= 0; i--) {
        	if(nums[i] < nums[i + 1])
        		break;
        }
        
        if(i == -1) {
        	reverse(nums, 0, nums.length - 1);
        	return;
        }
        
        j = findMinLarger(nums, i);//using binary search to find j.
        
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private int findMinLarger(int[] nums, int start) {
    	int target = nums[start++], end = nums.length;
    	int mid = start;
    	while(start < end) {
    		if(start == end - 1)
    			return start;
    		mid = (start + end) >>> 1;
        	if(nums[mid] > target) {
        		start = mid;
        	} else {
        		end = mid;
        	}
    	}
    	
        return mid;
    }
    
    private void reverse(int[] nums, int start, int end) {
    	int temp;
    	while(start < end) {
    		temp = nums[start];
    		nums[start++] = nums[end];
    		nums[end--] = temp;
    	}
    }
    

    }


Log in to reply
 

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