面试经典150题—

文章目录

1、数组中的第K个最大元素
- 1.1 题目链接
- 1.2 题目描述
- 1.3 解题代码
- 1.4 解题思路
2、IPO
- 2.1 题目链接
- 2.2 题目描述
- 2.3 解题代码
- 2.4 解题思路
3、查找和最小的 K 对数字
- 3.1 题目链接
- 3.2 题目描述
- 3.3 解题代码
- 3.4 解题思路
4、数据流的中位数
- 4.1 题目链接
- 4.2 题目描述
- 4.3 解题代码
- 4.4 解题思路

1、数组中的第K个最大元素

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

1.3 解题代码

class Solution {
    
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        bulidMaxHeap(nums, heapSize);
        for(int i = nums.length - 1; i >= nums.length - k + 1; --i){
            swap(nums, 0, i);
            --heapSize;
            maxHeapipy(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void bulidMaxHeap(int[] nums, int heapSize){
        for(int i =  heapSize / 2 - 1; i >= 0; --i){
            maxHeapipy(nums, i, heapSize);
        }
    }

    public void maxHeapipy(int[] nums, int i, int heapSize){
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if(l < heapSize && nums[l] > nums[largest]){
            largest = l;
        }
        if(r < heapSize && nums[r] > nums[largest]){
            largest = r;
        }
        if(largest != i){
            swap(nums, i, largest);
            maxHeapipy(nums, largest, heapSize);
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

1.4 解题思路

建立大根堆。

2、IPO

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

假设力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

提示：

1 <= k <= 10⁵
0 <= w <= 10⁹
n == profits.length
n == capital.length
1 <= n <= 10⁵
0 <= profits[i] <= 10⁴
0 <= capital[i] <= 10⁹

2.3 解题代码

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int res = w;
        int n = profits.length;
        int[][] nums = new int[n][2];
        for(int i = 0; i < n; ++i){
            nums[i][0] = profits[i];
            nums[i][1] = capital[i];
        }
        Arrays.sort(nums, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((x , y) -> y - x);
        int idx = 0;
        while(idx < n && w >= nums[idx][1]){
            pq.offer(nums[idx][0]);
            idx++;
        }
        while(k > 0 && !pq.isEmpty()){
            k--;
            int num = pq.poll();
            res += num;
            w += num;
            while(idx < n && w >= nums[idx][1]){
                pq.offer(nums[idx][0]);
                idx++;
            }
        }
        return res;
    }
}

2.4 解题思路

创建一个二维数组，存入每一个项目的利润和成本。并且将该二维数组按照成本非递减进行排序。
创建一个大根堆，利润高的项目在堆顶。
初始化最终利润为本金，每次取项目前现将满足条件（成本小于等于当前记录的最终利润）的项目放入大根堆中，每次取项目取栈顶即可。

3、查找和最小的 K 对数字

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

提示:

1 <= nums1.length, nums2.length <= 10⁵
-10⁹ <= nums1[i], nums2[i] <= 10⁹
nums1 和 nums2 均为 升序排列
1 <= k <= 10⁴
k <= nums1.length * nums2.length

3.3 解题代码

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<int []> pq = new PriorityQueue<>(k, (o1, o2)->{
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });
        int m = nums1.length;
        int n = nums2.length;
        for(int i = 0; i < Math.min(m, k); ++i){
            pq.offer(new int[]{i, 0});
        }
        while(!pq.isEmpty() && k > 0){
            k--;
            int[] idxPair = pq.poll();
            List list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            res.add(list);
            if(idxPair[1] < n - 1){
                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }
        return res;
    }
}

3.4 解题思路

贪心+优先队列。
优先队列以小根堆的形式，存放的数对下标，其对应的数对值最小的则在堆顶。设m为nums1数组的长度，n为nums2数组的长度，则先取的数对，第一个元素为nums1中前k（m）个元素（如果不足k个取m个）。
然后开始根据优先队列中的堆顶来取元素，记堆顶元素下标对为（x, y），则可能比堆里面的数小的数对中，最小的是{nums1[x], nums2[y + 1]} (只要y小于n - 1)。

4、数据流的中位数

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

提示:

-10⁵ <= num <= 10⁵
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10⁴ 次调用 addNum 和 findMedian

4.3 解题代码

class MedianFinder {
    PriorityQueue<Integer> maxQueue;// 大根堆
    PriorityQueue<Integer> minQueue;// 小根堆
    public MedianFinder() {
        // 保证大根堆中的元素数量大于等于小根堆中的元素数量
        maxQueue = new PriorityQueue<>(Comparator.reverseOrder());// 大根堆
        minQueue = new PriorityQueue<>();// 小根堆
    }
    
    public void addNum(int num) {
        if(maxQueue.isEmpty() || num <= maxQueue.peek()){
            maxQueue.offer(num);
            while(maxQueue.size() > minQueue.size() + 1){
                minQueue.offer(maxQueue.poll());
            }
        } else{
            minQueue.offer(num);
            while(maxQueue.size() < minQueue.size()){
                maxQueue.offer(minQueue.poll());
            }
        }
    }
    
    public double findMedian() {
        if(maxQueue.size() > minQueue.size()){// 优先队列中元素总和为
            return maxQueue.peek();
        } else{
            return (maxQueue.peek() + minQueue.peek()) / 2.0;
        }
    }
}

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

4.4 解题思路

用优先队列维持两个堆，一个为大根堆，一个为小根堆，保证大根堆中的元素数量大于等于小根堆中元素的数量，并且最多只能多出一个。
建两个堆是为了保证，大根堆中的元素都小于等于小根堆中的元素，如果元素总数为奇数的话，中位数就是大根堆的堆顶元素，如果为偶数的话，则是大根堆和小根堆堆顶的元素和取平均值。
对于插入数字而言，如果插入时大根堆为空或者插入的数小于等于大根堆的堆顶，则插入小根堆中（不影响两个堆的堆顶），此时如果大根堆的堆顶元素数量大于小根堆堆顶的元素数 + 1，则将大根堆的堆顶插入到小根堆中；如果插入时插入的数大于大根堆的堆顶，则插入小根堆中，如果大根堆中的元素个数小于小根堆中的元素个数，则将小根堆的堆顶插入进入大根堆中。