Sort

经典题目

41 First Missing Positive

Put each number in its right place. (a[0] = 0 + 1, a[1] = 1 + 1, etc.) For example, if a[2] = 1, then swap(2, 0)

public int firstMissingPositive(int[] nums) {
    if (nums == null || nums.length == 0) return 1;
    for (int i = 0; i < nums.length; i++) {
        int index = i;
        int value = nums[i];
        while (nums[i] <= nums.length && nums[i] >= 1 && nums[i] - 1 != i && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] - 1 != i) {
            return i + 1;
        }
    }
    return nums.length + 1;
}

215 Kth Largest Element in an Array

暴 力解，直接sort，然后返回。其次，我们可以用heap求解。最优解，用quickSort思想。

Method 1

// Sort the array: O(nlogn)
// Get nums[length - k]: O(1)
// T/O(nlogn)

Method 2

// PriorityQueue (minHeap), keep size of k: O(nlogk)
// Get the min: O(logk)
// T/O(nlogk + logk)

Method 3

// PriorityQueue (maxHeap), keep size of n - k + 1: ((n - k + 1)log(n - k + 1))
// Get the max: O(log(n - k + 1))
// T/O(nlog(n - k + 1))

Method 4

// Quicksort idea, find the pivot of position n - k, so that all numbers to the left of the pivot <= pivot
// all numbers to the right of the pivot >= pivot
// T:O(n)/O(n^2)

Method 5

// Shuffle the input array
// Quick sort
// T/O(n)
 public int findKthLargest(int[] nums, int k) {
    shuffle(nums);
    k = nums.length - k;
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) {
            return nums[k];
        } else if (pivotIndex < k) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
    return -1;
}

private void shuffle(int[] nums) {
    Random random = new Random();
    for (int i = nums.length - 1; i >= 0; i--) {
        int j = random.nextInt(i + 1);
        swap(nums, i, j);
    }
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int lo = left;
    int hi = right - 1;
    while (lo <= hi) {
        if (nums[lo] < pivot) {
            lo += 1;
        } else if (nums[hi] >= pivot) {
            hi -= 1;
        } else {
            swap(nums, lo, hi);
        }
    }
    swap(nums, lo, right);
    return lo;
}