My 18ms Solution For Next Permutation


  • 0
    B
    public void nextPermutation(int[] nums) {
        // reverse the array when the array is dec
    		final int STARTINDEX = 0;
    		int startIndex = -1;
    		// search the array from the nums.length - 1.
    		for (int i = nums.length - 2; i >= 0; i--) {
    			// when the number is inc, the num in the specific pos need 
    			// to be placed by the mimnum number which more than the specifc num
    			// in the last part of array
    			if (nums[i] < nums[i + 1]) {
    				for (int j = nums.length - 1; j > i; j--) {
    					if (nums[j] > nums[i]) {
    						swap(nums, i, j);
    						break;
    					}
    				}
    				// update the reverse begin index
    				startIndex = i + 1;
    				break;
    			}
    		}
    			
    		if (startIndex == -1) {
    			startIndex = STARTINDEX;
    		}
    		reverseArray(nums, startIndex);
    	}
    
    	private void reverseArray(int[] nums, int startIndex) {
    		for (int i = startIndex, j = nums.length - 1; i < j; i++, j--) {
    			swap(nums, i, j);
    		}
    	}
    
    	private void swap(int[] nums, int leftIndex, int rightIndex) {
    		nums[leftIndex] ^= nums[rightIndex];
    		nums[rightIndex] ^= nums[leftIndex];
    		nums[leftIndex] ^= nums[rightIndex];
    	}

Log in to reply
 

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