面试经典 150 题-堆

LeetCode 面试经典 150 题-堆

数组中的第K个最大元素

堆排序

1. 建立一个大小为K的最小堆。
2. 遍历数组中的剩余元素，如果它大于堆顶元素，则将堆顶元素删除，将当前元素加入。
3. 最后堆顶元素就是第k个最大元素。

堆操作：

• minHeapify(int[] nums, int index, int heapSize)
  • 获取左右子树索引，初始化最小索引为当前元素；
  • 如果左子节点存在且小于当前节点，则更新最小节点索引；
  • 如果右子节点存在且小于当前节点，则更新最小节点索引；
  • 如果最小节点索引不等于当前节点索引，则交换当前节点和最小节点，并继续调整最小堆；
• buildHeap(int[] nums, int heapSize)
  • 从最后一个非叶子节点开始，依次向前调整节点，保证以每个节点为根的子树都是小根堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 建立最小堆
        buildHeap(nums, k);
        // 遍历剩余元素
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > nums[0]) {
                swap(nums, i, 0);
                minHeapify(nums, 0, k);
            }
        }
        // 返回结果
        return nums[0];
    }

    // 最小堆化操作
    public void minHeapify(int[] nums, int index, int heapSize) {
        // 计算左右子树索引
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        // 如果左子节点存在且小于当前节点，则更新最小节点索引
        if (left < heapSize && nums[left] < nums[smallest]) {
            smallest = left;
        }
        // 如果右子节点存在且小于当前节点，则更新最小节点索引
        if (right < heapSize && nums[right] < nums[smallest]) {
            smallest = right;
        }
        // 如果最小节点索引不等于当前节点索引，则交换当前节点和最小节点，并继续调整最小堆
        if (smallest != index) {
            swap(nums, smallest, index);
            minHeapify(nums, smallest, heapSize);
        }
    }

    // 建立最小堆
    public void buildHeap(int[] nums, int heapSize) {
        // 从最后一个非叶子节点开始向前最小堆化
        for (int i = heapSize / 2; i >= 0; i--) {
            minHeapify(nums, i, heapSize);
        }
    }

    // 交换数组中的两个数
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

• 时间复杂度：O(nlogk)，建堆的时间是O(k)，O((n - k) * log k)。
• 空间复杂度：O(logk)，递归栈空间。

快速排序

快速选择函数：

递归地选择数组的一部分，通过分区操作（partition）来逐步缩小问题规模，直到找到第 k 大的元素。
通过基准元素将数组分为左右两部分，左边部分元素小于基准，右边部分元素大于基准。递归只会进入包含目标位置的一边。

分区操作（Partition）：

选择左边界的元素作为基准元素（pivot）。
使用两个指针从两边开始扫描，找到大于基准的元素与小于基准的元素，交换它们的位置。
最终，将基准元素放置在正确的位置（即它应该排在所有小于它的元素左边，大于它的元素右边）。
返回基准元素的位置 pivotIndex，该位置左边的元素都小于基准，右边的元素都大于基准。

递归选择：

如果基准元素的位置恰好是目标位置（即 pivotIndex == nums.length - k），则返回该元素。
如果基准元素的位置小于目标位置，则递归右边部分。
如果基准元素的位置大于目标位置，则递归左边部分。

牛客上有这道题，试试acm模式。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().replace("[", "").replace("]", "").split(",");
        int[] nums = new int[str.length];
        for (int i = 0; i < str.length; i++) {
            nums[i] = Integer.parseInt(str[i]);
        }
        System.out.println(findKthLargest(nums, 3));
    }

    public static int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    public static int quickSelect(int[] nums, int left, int right, int k) {
        int pivotIndex = partition(nums, left, right);
        int target = nums.length - k;
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (pivotIndex < target) {
            return quickSelect(nums, pivotIndex+1, right, k);
        } else {
            return quickSelect(nums, left, pivotIndex-1, k);
        }
    }

    public static int partition(int[] nums, int left, int right) {
        // 选择左边界元素作为基准元素
        int pivot = nums[left];
        // 初始化左右指针
        int i = left, j = right + 1;
        // 开始分区
        while (i < j) {
            // 从左往右找到第一个大于等于基准元素的元素
            while (++i < right && nums[i] < pivot);
            // 从右往左找到第一个小于等于基准元素的元素
            while (--j > left && nums[j] > pivot);
            // 分区完成
            if (i >= j) {
                break;
            }
            // 交换
            swap(nums, i, j);
        }

        // 将基准元素放置在正确的位置上
        swap(nums, left, j);
        return j;
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(logn)

IPO

利用堆的贪心算法

将项目按照所需资本的从小到大进行排序，每次进行选择时，假设当前手中持有的资本为 w，我们应该从所有投入资本小于等于 w 的项目中选择利润最大的项目 j，然后此时我们更新手中持有的资本为 w+profits[j]，同时再从所有花费资本小于等于 w+profits[j] 的项目中选择，按照上述规则不断选择 k 次即可。

利用大根堆的特性，我们将所有能够投资的项目的利润全部压入到堆中，每次从堆中取出最大值，然后更新手中持有的资本，同时将待选的项目利润进入堆，不断重复上述操作。

如果当前的堆为空，则此时我们应当直接返回。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 按照所需资本大小进行排序
        int n = profits.length;
        int cur = 0;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        
        // 大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        for (int i = 0; i < k; i++) {
            // 将所有需要资本小于w的利润加入队列
            while (cur < n && arr[cur][0] <= w) {
                pq.add(arr[cur][1]);
                cur++;
            }
            // 选择利润最大的那个
            if (!pq.isEmpty()) {
                w += pq.poll();
            } else {
                break;
            }
        }

        return w;
    }
}

• 时间复杂度：O((n+k)logn)，其中 n 是数组 profits 和 capital 的长度，k 表示最多的选择数目。我们需要 O(nlogn) 的时间复杂度来来创建和排序项目，往堆中添加元素的时间不超过 O(nlogn)，每次从堆中取出最大值并更新资本的时间为 O(klogn)。
• 空间复杂度：O(n)，其中 n 是数组 profits 和 capital 的长度。空间复杂度主要取决于创建用于排序的数组和大根堆。

查找和最小的K对数字

最小堆

1. 定义最小堆，存储两数和、两数下标。
2. 初始时放入nums1[0]和nums2[0]，这个数对一定是答案中最小的。
3. 对于优先队列：
   1. 弹出和最小的数对，获取其下标i和j，加入答案数组。
   2. 加入下一个元素，nums1[i+1]、nums2[j]和nums1[i]、nums2[j+1]。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // 初始化
        List<List<Integer>> ans = new ArrayList<>(k);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{nums1[0] + nums2[0], 0, 0});
        // 循环
        while (ans.size() < k) {
            int[] p = pq.poll();
            int i = p[1];
            int j = p[2];
            // 加入结果集
            ans.add(List.of(nums1[i], nums2[j]));
            // 下一个元素
            if (j == 0 && i + 1 < nums1.length) {
                pq.add(new int[]{nums1[i+1] + nums2[j], i+1, j});
            }
            if (j + 1 < nums2.length) {
                pq.add(new int[]{nums1[i] + nums2[j+1], i, j+1});
            }
        }
        return ans;
    }
}

• 时间复杂度：O(klogmin(n,k))，其中 n 为 nums1的长度。为了得到 k 个数对，需要循环 k 次，每次出堆入堆的时间复杂度为 logmin(n,k)。所以总的时间复杂度为 O(klogmin(n,k))。
• 空间复杂度：O(min(n,k))。堆中至多有 O(min(n,k)) 个三元组。

数据流中的中位数

堆

• 如果当前 left 的大小和 right 的大小相等：先把 num 加到 right 中，然后把 right 的最小值从 right 中去掉，并添加到 left 中。
• 如果当前 left 比 right 多 1 个数：先把 num 加到 left 中，然后把 left 的最大值从 left 中去掉，并添加到 right 中。

即left 是最大堆，right 是最小堆。

• 如果当前有奇数个元素，中位数是 left 的堆顶。
• 如果当前有偶数个元素，中位数是 left 的堆顶和 right 的堆顶的平均值。

class MedianFinder {
    private final PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);  // 最大堆
    private final PriorityQueue<Integer> right = new PriorityQueue<>((a, b) -> a - b);  // 最小堆

    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        // 分类讨论
        if (left.size() == right.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else {
            left.offer(num);
            right.offer(left.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        }
        return left.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

• 时间复杂度：初始化和 findMedian 都是 O(1)，addNum 是 O(logq)，其中 q 是 addNum 的调用次数。每次操作堆需要 O(logq) 的时间。
• 空间复杂度：O(q)

总结

要学会自己实现堆，包括堆化和建堆操作；学会使用封装好的PriorityQueue，可以通过重写比较函数实现最大堆和最小堆。