Leetcode算法题215：数组中第k大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

思路1：快排思想
快速排序是对冒泡的改进，降低冒泡的递归深度，使时间复杂度降低到O(nlgn)。因为快排每次将数组划分为两组加一个基准元素，每一趟划分你只需要将k与基准元素的下标进行比较。
如果比基准元素下标大就从右边的子数组中找，如果比基准元素下标小从左边的子数组中找，如果一样则就是基准元素，找到，
如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

- (int)findKthLargest:(NSMutableArray *)array k:(int)k {
    int i = 0;
    int j = (int)array.count - 1;
    while (true) {
        int temp = [self partition:array i:i j:j];//执行一遍后，把最大的放最前面，再比较temp和k的关系
        if (k == temp + 1) {
            return [array[temp] intValue];
        }else if(k < temp + 1)
        {
            j = temp-1;//这里每次要把基准元素去掉，否则会死循环
        }
        else
        {
            i = temp + 1;
        }
    }
}

- (int)partition:(NSMutableArray *)array i:(int)i j:(int)j {
    int pivot = [array[i] intValue];
    while (i != j) {
        while (i < j && [array[j] intValue] < pivot) {
            j--;
        }
        while (i < j && [array[i] intValue] > pivot) {
            i++;
        }
        if (i < j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    return i;
}

思路2：堆排序思想
建立最小根堆，用数组的前k个数，建立最小根堆。然后从第k+1开始，和堆顶比较，如果比堆顶大，就交换，交换完重新维护成最小根堆，直到结束。这样堆里存放的就是数组中前k个最大的元素，而堆顶就是这里面最小的，也就是第k大的元素。

- (int)findKthLargest:(NSMutableArray *)array k:(int)k {
    
    // 1.前k个数建立最小根堆，最小的数在堆顶
    NSMutableArray *newArr = [self buildHeap:[array subarrayWithRange:NSMakeRange(0, k)].mutableCopy n:k];
    // 2.从第k+1个开始，和堆顶比较
    for (NSInteger i = k; i < array.count; i++) {
        // 3.比堆顶大，则交换
        if ([array[i] intValue] > [newArr[0] intValue]) {
            newArr[0] = array[i];
            // 4.再对数组进行堆排序
            newArr = [self buildHeap:newArr n:k];
        }
    }

    return [newArr[0] intValue];
}

- (NSMutableArray *)buildHeap:(NSMutableArray *)array n:(NSInteger)n {
    NSInteger last = n - 1;
    NSInteger parent = (last - 1) / 2;
    for (NSInteger i = parent; i >= 0; i--) {
        [self heapify:array n:n i:i];
    }
    return array;
}

// heapify：小根堆思想，最小的放根位置
- (void)heapify:(NSMutableArray *)array n:(NSInteger)n i:(NSInteger)i {
    if (i >= n) {
        return;//递归出口
    }
    
    // 完全二叉树，根节点位置为i
    // 左子节点
    NSInteger c1 = 2*i + 1;
    NSInteger c2 = 2*i + 2;
    NSInteger min = i;
    
    if (c1 < n && [array[c1] intValue] < [array[min] intValue]) {
        min = c1;
    }
    if (c2 < n && [array[c2] intValue] < [array[min] intValue]) {
        min = c2;
    }
    if (min != i) {
        [array exchangeObjectAtIndex:min withObjectAtIndex:i];
        [self heapify:array n:n i:min];
    }
}

思路3：java的优先队列PriorityQueue
优先级队列，常用来代替堆，每次直接加入新数即可，自动维护大小顺序，最小的数在堆顶。数组中前k个元素加入到队列中，当k+1个进入后，最小的出队，这样数组遍历完后，队列中刚好剩下k个元素，返回堆顶元素就是第k大的元素

 public int findKthLargest(int[] nums, int k) {
     PriorityQueue<Integer> queue = new PriorityQueue<>();
     for (num:nums) {
         queue.offer(num);//入队
         if (queue.size() > k) {
             queue.poll();//堆顶最小的元素出队
         }
     }
     return queue.peak();//返回堆顶最小的元素
 }