Partition

Remove Duplicates from Sorted Array

题目要求的是in-place的来解决，而且只关心不重复的数字

利用partition的思想，维护一个没有重复的子数组的长度

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // error-prone, 最小值是1，而不是0
        int len = 1;

        for(int i = 1; i < nums.length; i++) {
            // i是第一个不重复的数
            if(nums[i] != nums[i - 1]) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }
}

Remove Duplicates from Sorted Array II

允许两个重复的元素

自然而然的想到了count计数，如果count大于2，那么就跳过这些数

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // 维护一个有效数组的长度
        int len = 1;
        int count = 1;

        for(int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[i - 1]) {
                count++;
                // 个数大于2的元素后面的就不要了
                if(count > 2) {
                    continue;
                }
            } else {
                count = 1;
            }
            nums[len++] = nums[i];
        } 
        return len;
    }
}

Quick Select

find the kth smallest element in an unordered list.

Difference with QuickSort Instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for.

 // Returns the k-th smallest element of list within left..right inclusive
public static int findKthSmallest(int[] nums, int k) {
    int left = 0;
    int right = nums.length - 1;
    k = k - 1; // change to base 0
    return quickSelect(nums, left, right, k);
}

public static int quickSelect(int[] nums, int left, int right, int k) {
    if(left == right) {
        return nums[left];
    }

    int pivotIndex = right; // select rightest num as pivot
    pivotIndex = partition(nums, left, right, pivotIndex);

    if(k == pivotIndex) {
        return nums[k];
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}

public static int partition(int[] nums, int left, int right, int pivotIndex) {
    int pivotVal = nums[pivotIndex];
    int start = left;
    for(int i = left; i < right; i++) {
        if(nums[i] < pivotVal) {
            swap(nums, i, start);
            start++;
        }
    }
    swap(nums, right, start);
    return start;
}

public static void swap(int[] nums, int n1, int n2) {
    int temp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = temp;
}
// Worst case performance  O(n^{2})
// Best case performance   O(n)
// Average case performance O(n)