算法：排序和搜索

75 颜色分类
快速排序：基于重复元素过多的问题，有双路排序和三路排序算法。
双路排序即最常用的写法：
参考：https://blog.csdn.net/k_koris/article/details/80585979

int partition(int* nums,int start,int end){
    int pivot = nums[start];
    while (start < end){
        while (nums[end] >= pivot && start<end)
            end--;
        if (nums[end] < pivot)
            nums[start] = nums[end];
        while (nums[start] <= pivot && start<end)
            start++;
        if (nums[start] > pivot)
            nums[end] = nums[start];
    }
    nums[start] = pivot;
    return start;
}

void quick(int* nums,int start,int end){
    if (start < end){
        int k = partition(nums,start,end);
        quick(nums,start,k-1);
        quick(nums,k+1,end);
    }
}

三路排序：使用 lt、gt 分别表示小于、大于pivot值的边界，i 表示当前移动的值；将数组分成小于、等于、大于pivot的三部分，再进行递归快排。

void __quicksort3(T arr[],int l,int r){
    if(l>=r)
    return ;
    
    T v=arr[l];
    int lt=l;
    int gt=r+1;
    int i=l+1;
    while(i<gt){
        if(arr[i]<v){
            swap(arr[i],arr[lt+1]);
            lt++;
            i++;
        }
        else if(arr[i]>v){
            swap(arr[i],arr[gt-1]);
            gt--;
        }
        else
            i++;
    }
    swap(arr[l],arr[lt]);
     __quicksort3(arr,l,lt-1);
     __quicksort3(arr,gt,r);
}

88 合并两个有序数组
数组移动数据时，从已有数组区从空白区填充。
34 在排序数组中查找元素的第一个和最后一个位置
分治法：
循环条件用left<=right；
依据中点值分配左右区时，判断中点是否应该再算入左右区，以避免对中点前后的多次判断；
对数组0和len-1值的处理应该放到if(mid符合条件)条件下，而不是另外作判断。

// 二分查找排序数组中某元素的第一个位置
while (left <= right){
    int mid = left + (right-left)/2;
    if (nums[mid]==target){
        if (mid==0||nums[mid-1]<target){
            tl = mid;
            break;
        }else
            right = mid-1;
    }else if(nums[mid]>target){
        right = mid-1;
    }else{
        left = mid+1;
    }
}
if (tl==-1) return res;

215 数组中的第K个最大元素
类似第k个最大这种题型：第K个最大用小根堆，最小用大根堆。优先队列可以用堆实现，堆本质是完全二叉树，可以用数组实现。堆化操作时间复杂度O(logn).

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue();
    for (int i=0;i<nums.length;i++){
        if (heap.size() == k){
            if (heap.peek() < nums[i])
                heap.poll();
            else
                continue;
        }
        heap.add(nums[i]); // java PriorityQueue默认是小根堆
    }
    return heap.peek();
}

56 合并区间
并查集：参考https://www.jianshu.com/p/b37ba1f7d45c

def merge(self, intervals: List[Interval]) -> List[Interval]:
    if intervals == []: return []
    intervals.sort(key=lambda p:p.start) // 先按start进行排序
    rst = []
    tmp = intervals[0]
    for i in intervals: // 遍历所有区间，若当前区间start<=所求集合已有的最末元素的end，则合并
        if i.start <= tmp.end:
            if tmp.end <= i.end:
                tmp.end = i.end
        else: // 否则将其加入所求集合
            rst.append(tmp)
            tmp = i
    rst.append(tmp)
    return rst

240 搜索二维矩阵 II
分治法 II:
可以利用nums[left], nums[right], nums[mid] 协助判断；
二维矩阵搜索：利用矩阵左上(sx,sy)和右下角(ex,ey)元素作为定位，中间元素为((sx+ex)/2,(sy+ey)/2), 并用中点的上下左右点(sx,ny), (ex,ny), (nx,sy), (nx,ey)协助确定下一次搜索的子矩阵。

最后编辑于：2019.04.23 16:20:19