Modified quicksort gets time limit exceeded


  • 0
    C

    Using HashSet is the only way?

    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            return hasDuplicate(nums, 0, nums.length - 1);
        }
        
        private boolean hasDuplicate(int[] nums, int lo, int hi) {
            if (lo >= hi) {
                return false;
            }
            int p = partition(nums, lo, hi);
            if (p == -1) {
                return true;
            }
            
            return hasDuplicate(nums, lo, p - 1) || hasDuplicate(nums, p + 1, hi);
        }
        
        private int partition(int[] nums, int lo, int hi) {
            int pivot = nums[hi];
            int i = lo;
            for(int j = lo; j < hi; j ++) {
                if (nums[j] == pivot) {
                    return -1;
                }
                if (nums[j] < pivot) {
                    swap(nums, i, j);
                    i ++;
                }
            }
            swap(nums, i, hi);
            return i;
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

Log in to reply
 

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