马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
1、数组中的第K个最大元素
1.1 题目链接
点击跳转到题目位置
1.2 题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你必要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法办理此问题。
提示：
- 1 <= k <= nums.length <= 105
- -104 <= nums <= 104
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;
- }
- }
2、IPO
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增长其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits ，和启动该项目必要的最小资本 capital 。
最初，你的资本为 w 。当你完成一个项目时，你将得到纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可得到的最多资本。
答案保证在 32 位有符号整数范围内。
提示：
- 1 <= k <= 105
- 0 <= w <= 109
- n == profits.length
- n == capital.length
- 1 <= n <= 105
- 0 <= profits <= 104
- 0 <= capital <= 109
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;
- }
- }
- 创建一个二维数组，存入每一个项目的利润和成本。并且将该二维数组按照成本非递减举行排序。
- 创建一个大根堆，利润高的项目在堆顶。
- 初始化最终利润为本金，每次取项现在现将满意条件（成本小于便是当前纪录的最终利润）的项目放入大根堆中，每次取项目取栈顶即可。
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 <= 105
- -109 <= nums1, nums2 <= 109
- nums1 和 nums2 均为 升序排列
- 1 <= k <= 104
- 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;
- }
- }
- 贪心+优先队列。
- 优先队列以小根堆的情势，存放的数对下标，其对应的数对值最小的则在堆顶。设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 以内的答案将被接受。
提示:
- -105 <= num <= 105
- 在调用 findMedian 之前，数据结构中至少有一个元素
- 最多 5 * 104 次调用 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();
- */
- 用优先队列维持两个堆，一个为大根堆，一个为小根堆，保证大根堆中的元素数目大于便是小根堆中元素的数目，并且最多只能多出一个。
- 建两个堆是为了保证，大根堆中的元素都小于便是小根堆中的元素，如果元素总数为奇数的话，中位数就是大根堆的堆顶元素，如果为偶数的话，则是大根堆和小根堆堆顶的元素和取平均值。
- 对于插入数字而言，如果插入时大根堆为空大概插入的数小于便是大根堆的堆顶，则插入小根堆中（不影响两个堆的堆顶），此时如果大根堆的堆顶元素数目大于小根堆堆顶的元素数 + 1，则将大根堆的堆顶插入到小根堆中；如果插入时插入的数大于大根堆的堆顶，则插入小根堆中，如果大根堆中的元素个数小于小根堆中的元素个数，则将小根堆的堆顶插入进入大根堆中。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
