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

Method 3

Method 4

Method 5