Partition

Partition-array
Partition Array by Odd and Even
Sort Letters by Case
quick sort/ quick select/ nuts bolts problem/wiggle sort II

• 本身就是O(n)

Sort Colors

• 目标是确定不同值的下标位置，只有最后的位置是有关的。所以可以通过遍历每个值来更新每个值的计数，可以通过override的方式，确保值被更新成最终想要的

public void sortColors(int[] nums) {
        int n0 = 0, n1 = 0, n2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[n2++] = 2;
                nums[n1++] = 1;
                nums[n0++] = 0;
            } else if (nums[i] == 1) {
                nums[n2++] = 2;
                nums[n1++] = 1;
            } else {
                nums[n2++] = 2;
            }                
        }   
    }

• 本身就是O(n)

  Quick Select

  回忆快排中的操作

• 取一个pivot，左边比pivot小，右边比pivot大
• 那么由右边的个数，即可知道pivot是第几大的，进而知道第k大的在左边或者右边
• 就可以丢掉一部分，然后找到剩下部分第k-l大的

具体进行partition

1. 随机取一个pivot，把pivot和第一个元素交换
2. 将数组第一个位置设为空
3. right指针从右往左扫，找到第一个比pivot大的，放到第一个位置 (相等时候直接跳过，为了避免变成n^2）
4. left指针从左往右扫，找到第一个比pivot小的，放回最后一个位置
5. 不断重复3，4，直到left，right指针最后都指向了那个空的位置，将pivot填入
6. 接下来可以确定，第kth在左侧或者右侧

worst case O(n^2), average O(n)

public int partition (int[] nums, int l, int r) {
    //初始化左右指针
    int left = l, right = r;
    int pivot = nums[left];

    //进行partition
    while (left < right) {
        while (left < right && nums[right] >= pivot) {
            right--; // find the first smaller
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        nums[right] = nums[left];
    }

    //返还pivot点到数组里面
    nums[left] = pivot;
    return left;
}

kth largest element

几种思路

1. 排序，取第kth O(nlogn)

2. 创建一个k个元素的heap，每次把heap里最小的元素排出 O(nlogk)

3. 更适合求前k个元素

   1. Quick Select

Nuts and Bolts problems

几种思路

1. two for loops, O(n^2)
2. partition, 两个数组不断互相的进行partition排序O(nlogn)

Product of Array Except Self

• 通过算左边和右边的乘积
• 空间上还可以优化，把左边乘积放入res，右边乘积只有2个值不断前滚

  public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    for (int i = 0, tmp = 1; i < nums.length; i++) {
        result[i] = tmp;
        tmp *= nums[i];
    }
    for (int i = nums.length - 1, tmp = 1; i >= 0; i--) {
        result[i] *= tmp;
        tmp *= nums[i];
    }
    return result;
  }