java O(n) and O(nlogn) methods


  • 0
    T

    O(nlogn)

    public static int findUnsortedSubarray(int[] nums) {
    		int[] ori = new int[nums.length];
    		System.arraycopy(nums, 0, ori, 0, nums.length);
    		;
    		Arrays.sort(nums);
    		int min = nums.length;
    		int max = 0;
    		for (int i = 0; i < nums.length; i++) {
    			if (ori[i] != nums[i]) {
    				min = i;
    				break;
    			}
    
    		}
    		for (int j = nums.length - 1; j >= 0; j--) {
    			if (ori[j] != nums[j]) {
    				max = j;
    				break;
    			}
    		}
    
    		if (min > max)
    			return 0;
    		else
    			return max - min + 1;
    	}
    

    O(nlogn) method

    	public static int findUnsortedSubarray2(int[] nums) {
    		int min = Integer.MAX_VALUE;
    		int max = Integer.MIN_VALUE;
    		int left = nums.length, right = 0;
    		for (int i = 1; i < nums.length; i++) {
    			if (nums[i - 1] > nums[i] && nums[i] < min) {
    				min = nums[i];
    			}
    		}
    
    		for (int i = nums.length - 1; i >= 1; i--) {
    			if (nums[i - 1] > nums[i] && nums[i - 1] > max) {
    				max = nums[i - 1];
    			}
    		}
    
    		for (int i = 0; i < nums.length; i++) {
    			if (nums[i] > min) {
    				left = i;
    				break;
    			}
    		}
    		for (int i = nums.length - 1; i >= 1; i--) {
    			if (nums[i] < max) {
    				right = i;
    				break;
    			}
    		}
    
    		if (right < left)
    			return 0;
    		else
    			return right - left + 1;
    	}

Log in to reply
 

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