6/13, Two Pointers，对撞型，partition类
Kth Largest Element in an Array
partition 类双指针
public class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length-1, nums.length-k); //key point: Kth largest
}
public int quickSelect(int[] nums, int left, int right, int k){
while(left<=right){
int x = partition(nums, left, right);
if(x==k) return nums[x];
else if(x<k){
left = x+1;
}
else
right = x-1;
}
return -1;
}
public int partition(int[] nums, int start, int end){
Random rnd = new Random();
int pivot = rnd.nextInt(end-start+1)+start;
swap(nums, start, pivot);
int left = start+1; pivot = start; int right = end;
while(left<=right){
while(left<=right && nums[left]<=nums[pivot]) left++;
while(left<=right && nums[right]>=nums[pivot]) right--;
if(left<=right)
swap(nums, left++, right--);
}
swap(nums, right, pivot);
return right;
}
public void swap(int[] nums, int start, int end){
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
}
}
Sort Colors
非常有名的算法，人称“荷兰旗算法”Dutch national flag problem，经典的 "3-way partitioning"算法，用于解决 quick sort 类排序算法中对于重复元素的健壮性问题，在原有 2-way partitioning 的基础上把所有 val == key 的元素集中于数组中间，实现【（小于），（等于），（大于）】的分区。
一张图说明 Dijkstra 的 3-way partitioning，左右指针维护 < key 和 > key 的元素，[left , cur - 1] 为 = key 的元素，[cur, right] 为未知元素。
只有在和 right 换元素时，cur 指针的位置是不动的，因为下一轮还要看一下换过来的元素是不是 < key 要放到左边。
O(n) 时间复杂度
public class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
int i = 0;
while(i <= right){
if(nums[i] < 1){
swap(nums, left++, i++);
} else if(nums[i] > 1){
swap(nums, i, right--);
} else {
i ++;
}
}
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
Sort Colors II
3-way partition 的进阶版本，k-way partition. (FB面经)
利用已知最大和最小 key，维护双指针对撞
数组结构是
【最小key】【cur + unknown】【最大key】
这种写法的复杂度分析稍微麻烦一些，最大为 O(n * k/2) 每次复杂度上限为O(n)，最多进行 k / 2 次循环，然而要考虑每次迭代会固定去掉头尾两部分数组，导致 n 逐渐变小，实际的复杂度要根据 k 个数字的分部情况来看，k 的分布越偏向于【1，k】 的两侧，复杂度就越低。
永远用小于等于判断 left<=right
public void sort(int[] n, int start, int end, int k){
if(k<2||start>end||n.length==0) return;
int min=Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
for(int i=start;i<=end;i++){
min = Math.min(min, n[i]);
max = Math.max(max, n[i]);
}
int left = start; int right = end; int low = start;
while(left<=right){
if(n[left]==min){
swap(n, left, low);
low++;left++;
}
else if(n[left]>min&&n[left]<max)
left++;
else{
swap(n, left, right);
right--;
}
}
sort(n, low, right, k-2);
}
recursive 93% test cases后超时了; 尾递归改循环
public void sortColors2(int[] colors, int k){
int left = 0; int right = colors.length-1;
int low = 0; int lowKey = 1; int highKey = k;
while(lowKey<highKey){
left = low;
while(left<=right){
if(colors[left]==lowKey){
swap(colors, left, low);
low++;left++;
}
else if(colors[left]==highKey){
swap(colors, left, right);
right--;
}
else{
left++;
}
}
lowKey++;
highKey--;
}
}
public void swap(int[] n, int i, int j){
int tmp = n[i];
n[i]=n[j];
n[j]=tmp;
}
Sort Letters by Case
顺着 3-way partitioning 的思路，其实这种写法也很适合解决 2-way partitioning 的问题。
public class Solution {
/**
*@param chars: The letter array you should sort by Case
*@return: void
*/
public void sortLetters(char[] chars) {
//write your code here
int left = 0;
int right = chars.length - 1;
int cur = 0;
while(cur <= right){
if(chars[cur] >= 'a'){
swap(chars, cur ++, left ++);
} else if(chars[cur] < 'a'){
swap(chars, cur, right--);
} else {
cur ++;
}
}
}
private void swap(char[] chars, int a, int b){
char temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
return;
}
}
2-way partitioning
swap的时候记住判断 if(left<=right), 否则有可能当left>right时swap
"DERLKAJKFKLAJFKAKLFJKLJFa" 输出"DaERLKAJKFKLAJFKAKLFJKLJF", left=1, right=0, 交换了s[0]和s[1]的元素
public void sortLetters(char[] chars) {
//write your code here
int left = 0; int right = chars.length-1;
while(left<=right){
while(left<=right && chars[left]>='a') left++;
while(left<=right && chars[right]<'a') right--;
if(left<=right)
swap(chars, left, right);
left++;right--;
}
}
private void swap(char[] chars, int a, int b){
char temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
return;
}
Sort Colors
这道题在left指针指向high时，实际上只要和right指针直接交换就可以，让right指针递减；这样即使right指针开始指向的是high，swap过后right－－；left指针会和（right－1）的位置再一次交换。
这道题关键是指针i在指向low的时候，和low指针所指向的交换，Pointer low＋＋，i＋＋； 而指向high时，和high指针指向交换，Pointer high－－，而i不变。
Split Array with Equal Sum
这个题没有别的办法，必须要至少枚举i,j,k三个数。求array sum的题首先要想到对array构建sum数组。枚举时，以j为中点，用i分割前半部分；以k为中点，分割后半部分。hashset记录sum，后半部分出现重复的sum就return true。这样的优点是利用hashset的空间存储，枚举三个变量空间复杂度从O(n^3)降到了O(n^2).
public class Solution {
public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int j = 3; j < nums.length - 3; j++) {
HashSet < Integer > set = new HashSet < > ();
for (int i = 1; i < j - 1; i++) {
if (sum[i - 1] == sum[j - 1] - sum[i])
set.add(sum[i - 1]);
}
for (int k = j + 2; k < nums.length - 1; k++) {
if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))
return true;
}
}
return false;
}
}