my java solution


  • 0
    X

    public class Solution {
    public void nextPermutation(int[] nums){
    if(nums==null || nums.length==0){
    return;
    }
    int i,j;
    boolean ismax=true; //判断是否已经是最大排列了

    	int len=nums.length;
    	int start=0	;	//快速排列的起始位置
    	int last;          //记录待对比的元素
    	int temp_min=nums[0];
    	for(i=1;i<len;i++){
    		if(nums[i]>temp_min){
    			ismax=false;
    			break;
    		}
    		else{
    			temp_min=nums[i];
    		}
    	}
    	if(ismax){
    		for(i=0,j=len-1;i<j;i++,j--){
    			int t=nums[i];
    			nums[i]=nums[j];
    			nums[j]=t;
    		}
    	}
    	else{
    		//记录待交换的位置分别为besti和bestj
    		int besti=-1,bestj=len-1;
    		for(j=len-1;j>=0;j--){
    			last=nums[j];
    			for(i=j-1;i>=0;i--){
    				if(last>nums[i]){
    					if(besti<i){
    						besti=i;
    						bestj=j;
    						break;
    					}	
    				}
    			}
    		}
    		int t=nums[besti];
    	        nums[besti]=nums[bestj];
    		nums[bestj]=t;
    
    		if(besti+1<len-1){
    			quickSort(nums,besti+1,len-1);
    		}
    	}	
    }
    public void quickSort(int[] nums,int low,int high){
    	if(low<high){
    		int middle=getMiddle(nums,low,high);
    		quickSort(nums,low,middle-1);
    		quickSort(nums,middle+1,high);
    	}	
    }
    public int getMiddle(int[] nums,int low,int high){
    	int temp=nums[low];
    	while(low<high){
    		while(low<high && nums[high]>temp){
    			high--;
    		}
    		nums[low]=nums[high];
    		while(low<high && nums[low]<=temp){
    			low++;
    		}
    		nums[high]=nums[low];
    	}
    	nums[low]=temp;
    	return low;
    }
    

    }


Log in to reply
 

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