5.5LeetCode

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        while (true) {
            int pos = help(left,right,nums);
            if (pos == k - 1) return nums[pos];
            else if (pos > k - 1) right = pos - 1;
            else left = pos + 1;
        }
    }
    public int help(int left,int right, int[] nums){
        int pivot = nums[left], l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                int temp=nums[l]; nums[l]=nums[r]; nums[r]=temp;
                l++;
                r--;
            }
            if ( nums[l] >= pivot) ++l;
            if (nums[r] <= pivot) --r;
        }
        int temp=nums[r];
        nums[r]=nums[left];
        nums[left]=temp;
        return r;
    }
}

class Solution {
    //堆排序的过程就是首先构建大根堆，然后对顶元素（及最大元素）与最后个元素替换位置，heapsize减一，重新调整堆变成大根堆。
    //重复上面操作直到heapsize等于一的时候。排序完成。
    public int findKthLargest(int[] nums, int k) {
        // 建一个大小为k+1(第一个结点不使用)的数组
        int[] heap = new int[k+1];  
         for(int i = 0; i < k; i++){
            heap[i+1] = nums[i];
        }
        
        // 堆化。建立一个大小为k的小顶堆
        // 从最后一个非叶子结点k/2自上往下开始进行堆化，该结点堆化完后就轮到前一个非叶子结点再自上往下进行堆化
        for(int i = k/2; i > 0; i--){
            heapify(heap,k+1,i);
        }       
        // 继续遍历数组中剩余的数字，并与堆顶元素进行比较，
        // 若大于堆顶元素，则替换掉堆顶元素，并自顶向下堆化
        for(int i = k; i < nums.length; i++){
            if(nums[i] > heap[1]){
                heap[1] = nums[i];
                heapify(heap,k+1,1);
            }
        }
        return heap[1];
    }
    // 自顶向下堆化。一般在删除堆顶结点后，把最后一个结点放到堆顶的时候使用。
    // 即这时堆中已经是部分堆化
    private void heapify(int[] heap,int len,int index){
        while(true){
            // 找出当前结点和两个直接子结点的最小值
            int minPos = index;   
            if(2*index < len && heap[2*index] < heap[minPos]){
                minPos = 2*index;
            }
            if(2*index+1 < len && heap[2*index+1] < heap[minPos]){
                minPos = 2*index + 1;
            }
            // 若当前结点是最小的，说明下面的是堆化好的了，直接退出循环
            if(minPos == index){
                break;
            }
            // 当前结点与最小值进行交换
            swap(heap,index,minPos);
            // 当前结点更改为最小直接子结点，继续往下堆化
            index = minPos;
        }
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        map<int,int> hashmap;
        for(int i=0;i<intervals.size();i++){
            auto it=hashmap.find(intervals[i][0]); //处理该区间起点
            if(it==hashmap.end()) //先前未访问过该结点
                hashmap[intervals[i][0]]=1;
            else hashmap[intervals[i][0]]++;
            it=hashmap.find(intervals[i][1]);  //处理区间终点
            if(it==hashmap.end())  //先前未访问过
                hashmap[intervals[i][1]]=-1;
            else hashmap[intervals[i][1]]--;
        }
        for(auto it=hashmap.begin();it!=hashmap.end();it++){
            vector<int> temp;
            temp.push_back(it->first);
            int cnt=0;
            while(1) {
                cnt+=it->second;
                if(cnt<=0) break;
                it++;
            }
            temp.push_back(it->first);
            res.push_back(temp);
        }
        return res;
    }
};

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0) return false;
        int m=matrix.length;
        int n=matrix[0].length;
        return help(matrix,0,n-1,0,m-1,target);
    }
    public boolean help(int[][] matrix,int left,int right,int top,int button,int target){
        //System.out.println(left+"+"+right+"+"+top+"+"+button);
        if(left<0||right>=matrix[0].length||top<0||button>=matrix.length||left>right||top>button) return false;
        if(left==right&&top==button) return (matrix[top][right]==target);
        if(right-left==1&&button-top==1) return matrix[top][left]==target||matrix[top][right]==target||matrix[button][left]==target||matrix[button][right]==target;
        if(right-left==1&&button==top) return matrix[top][left]==target||matrix[top][right]==target;
        if(button-top==1&&right==left) return matrix[button][left]==target||matrix[top][left]==target;
        int midi=(top+button)/2;
        int midj=(left+right)/2;
        //System.out.println(midi+"+"+midj);
        if(matrix[midi][midj]==target) return true;
        else if(matrix[midi][midj]>target){
            boolean t=help(matrix,left,midj,top,midi,target);
            if(t) return true;
            if(matrix[midi][left]<=target)
                t=help(matrix,left,midj-1,midi+1,button,target);
            if(t) return true;
            if(matrix[top][midj]<=target)
                t=help(matrix,midj+1,right,top,midi-1,target);
            if(t) return true;
        }
        else if(matrix[midi][midj]<target){
            boolean t=help(matrix,midj,right,midi,button,target);
            if(t) return true;    
            if(matrix[button][midj]>=target)
                 t=help(matrix,left,midj-1,midi+1,button,target);
            if(t) return true;
            if(matrix[midi][right]>=target)
                t=help(matrix,midj+1,right,top,midi-1,target);
            if(t) return true;
        }
        return false;
    }
}