Is this O(N) or O(NlogN)


  • 0
    R
    public class Solution {
    public void nextPermutation(int[] num) {
    
        int cur = num.length - 1;
        
        while(cur > 0) {
            if(num[cur - 1] < num[cur]) {
                int minIndex = num.length - 1;
                while(num[minIndex] <= num[cur - 1]){
                    minIndex --;
                }
                swap(num, cur - 1, minIndex);
                while(minIndex < num.length - 1 && num[minIndex] < num[minIndex + 1]){
                    swap(num, minIndex, minIndex + 1);
                    minIndex ++;
                }
                reverse(num, cur, num.length - 1);
                break;
            }
            cur --;
        }
        
        if(cur == 0) reverse(num, 0, num.length - 1);
    }
    
    private void reverse(int[] num, int start, int end) {
        while(start < end) {
            swap(num, start, end);
            start ++;
            end --;
        }    
    }
    
    private void swap(int[] num, int index1, int index2){
        if(index1 != index2) {
            num[index1] = num[index1]^num[index2];
            num[index2] = num[index1]^num[index2];
            num[index1] = num[index1]^num[index2];
        }
    }
    

    }


Log in to reply
 

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