leetcode 215. Kth Largest Element in an Array | 215. 数组中的第K个最大元素（Java）

ゞ浴缸里的玫瑰 2022-10-07 00:52 187阅读 0赞

## 题目 ##

[https://leetcode.com/problems/kth-largest-element-in-an-array/][https_leetcode.com_problems_kth-largest-element-in-an-array]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

--------------------

## 题解 ##

本题需要建立大顶堆。关于堆的数据结构，需要知道：

## 堆 ##

#### 什么是堆？ ####

**堆** 是一棵 **完全二叉树**：即使它不是满二叉树，也是正在从左往右变满的过程中。

1）堆结构就是用数组实现的完全二叉树结构

2）完全二叉树中，如果每棵子树的 **最大值都在顶部**，是 **大根堆**

3）完全二叉树中，如果每棵子树的 **最小值都在顶部**，是 **小根堆**

4）堆结构的 heapInsert 与 heapify 操作

5）堆结构的增大和减少

6）优先级队列结构，就是堆结构

7）特点：由 N 个数 组成的堆，高度是 log(n)

#### 如何用数组存放堆？ ####

##### 如果从 0 位置开始： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

i 层，则

*  左孩子：2 \* i + 1
 *  右孩子：2 \* i + 2
 *  父节点：(i - 1) / 2

##### 如果从 1 位置开始： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

正是由于可以使用 **位运算** 来代替 **算数运算**，效率更高，所以有时候让下标从 1 开始。

*  左孩子：2 \* i （i << 1）
 *  右孩子：2 \* i + 1 （i << 1 | 1）
 *  父节点：i / 2 （i >> 1）

#### 如何将数组转化成大根堆？—— heapInsert 操作 ####

每在 i 位置加入一个新的节点，都与它的 (i - 1) / 2 位置的父节点比较，如果比父节点大，则交换（并while比较父节点与父父节点）

private void heapInsert(int[] arr, int index) { 
        while (arr[index] > arr[(index - 1) / 2]) { 
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    private void swap(int[] arr, int i, int j) { 
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

#### 如何返回并删除大根堆的最大值，剩余数字依然保持大根堆？—— heapify 操作 ####

1.  将顶部元素取出
2.  将大根堆的最后位置上的元素覆盖到顶部
3.  while 循环
    
    1.  如果左右孩子中较大的数比当前节点更大，则交换当前节点和较大的孩子节点
    2.  如果左孩子下标越界，或左右孩子都不比当前节点大，就停止

// 返回最大值，并在大根堆中把最大值删掉，剩下的数依然保持大根堆形态
    public int pop() { 
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }
    // 从index位置开始，不断的下沉，直到我的孩子都不再比我大，或者我已经没孩子了，就停止
    private void heapify(int[] arr, int index, int heapSize) { 
        int left = index * 2 + 1;
        while (left < heapSize) { 
            // largest存储左右孩子 较大者 的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // largest存储两个孩子与父节点 较大者 的下标
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {  // 不需要交换的情况
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

#### 堆排序 ####

1.  先让整个数组都变成大根堆结构，建立堆的过程:
    
    1.  从上到下的方法，时间复杂度为O(N\*logN)
    2.  从下到上的方法，时间复杂度为O(N)
2.  把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N\*logN)
3.  堆的大小减小成0之后，排序完成！

public static void heapSort(int[] arr) { 
        if (arr == null || arr.length < 2) { 
            return;
        }
        // 方法1：对数组进行堆排序 O(N*logN)
        for (int i = 0; i < arr.length; i++) {  // O(N)
            heapInsert(arr, i); // O(logN)
        }
        // 方法2：仅将数组转化成大顶堆 O(n) 
        for (int i = arr.length - 1; i >= 0; i--) { 
            heapify(arr, i, arr.length);
        }
    }

--------------------

## 本题代码 ##

class Solution { 
        int[] nums;
        int heapSize;
    
        public int findKthLargest(int[] nums, int k) { 
            this.nums = nums;
            this.heapSize = nums.length;
            // 先让整个数组变成大根堆结构
            // 方法1：从上至下 对数组进行堆排序 O(N*logN)
    // for (int i = 0; i < nums.length; i++) // O(N)
    // heapInsert(nums, i); // O(logN)
            // 方法2：从下至上 仅将数组转化成大顶堆 O(N)
            for (int i = nums.length - 1; i >= 0; i--)
                heapify(nums, i, nums.length);
    
            int result = -1;
            for (int i = 0; i < k; i++)
                result = pop();
            return result;
        }
    
        public int pop() { 
            int max = nums[0];
            swap(nums, 0, --heapSize);
            heapify(nums, 0, heapSize);
            return max;
        }
    
        // 方法1 从上至下调整堆：每在i位置加入一个新的节点，都与它的(i-1)/2位置的父节点比较，如果比父节点大，则交换（并while比较父节点与父父节点）
        private void heapInsert(int[] arr, int index) { 
            while (arr[index] > arr[(index - 1) / 2]) { 
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        // 方法2 从下至上调整堆：从index位置开始，不断的下沉，直到我的孩子都不再比我大，或者我已经没孩子了，就停止
        public void heapify(int[] arr, int i, int heapSize) { 
            int left = i * 2 + 1;
            while (left < heapSize) { 
                int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left; // 左右孩子较大者的下标
                largest = nums[largest] > nums[i] ? largest : i; // 两个孩子与父节点较大者的下标
                if (largest == i) break; // 不需要交换的情况
                swap(arr, largest, i);
                i = largest; // 更新i使其下沉
                left = 2 * i + 1;
            }
        }
    
        private void swap(int[] arr, int i, int j) { 
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_kth-largest-element-in-an-array]: https://leetcode.com/problems/kth-largest-element-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/d6603e929edb474eb4a3559ba8a32b7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/1963fdbb110642f89c6d961fc5fff541.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/bca2d83bd9e345f6b896995179cc822a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/37867a98f5ef468ba58baa1149011d01.png