LeetCode（Heap)2099. Find Subsequence of Length K With the Largest Sum

客官°小女子只卖身不卖艺 2023-09-24 22:48 82阅读 0赞

# 1.问题 #

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

> Input: nums = \[2,1,3,3\], k = 2  
> Output: \[3,3\]

> Explanation:  
> The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

> Input: nums = \[-1,-2,3,4\], k = 3  
> Output: \[-1,3,4\]

> Explanation:  
> The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

> Input: nums = \[3,4,3,3\], k = 2  
> Output: \[3,4\]

> Explanation:  
> The subsequence has the largest sum of 3 + 4 = 7.  
> Another possible subsequence is \[4, 3\].

Constraints:

1 <= nums.length <= 1000  
\-105 <= nums\[i\] <= 105  
1 <= k <= nums.length

# 2. 解题思路 #

## 方法1： ##

> 1.优先队列用于排序,list方便添加删除  
> 2.遍历，将nums的元素添加到队列和list  
> 3.定义ans的数组，长度为k  
> 4.nums的长度减去k的长度也就是说需要取出的元素个数，pq已经排序的数据，删除队列头元素，并删除list的元素，也就是最后符合要求的元素  
> 5.获得list元素并放入数组ans中  
> 6.返回ans数组

## 方法2： ##

> 使用优先队列的方式

## 方法3： ##

> 使用链表的方式

# 3. 代码 #

## 代码1： ##

public int[] maxSubsequence(int[] nums, int k) {
        
           PriorityQueue<Integer> pq=new PriorityQueue<>();//1.优先队列用于排序,list方便添加删除
            List<Integer> list=new ArrayList<>();
            for(int n:nums){
        //2.遍历，将nums的元素添加到队列和list
                pq.add(n);
                list.add(n);
            }
    
            int[] ans=new int[k];//3.定义ans的数组，长度为k
    
            for(int i=0;i<nums.length-k;i++)
                //4.nums的长度减去k的长度也就是说需要取出的元素个数，pq已经排序的数据，删除队列头元素，并删除list的元素，也就是最后符合要求的元素
                list.remove(pq.remove());
    
            for(int i=0;i<k;i++)
                //5.获得list元素并放入数组ans中
                ans[i]=list.get(i);
    
            return ans;//6.返回ans数组
        }

### 本地代码运行 ###

import java.util.*;
    import java.util.LinkedList;
    import java.util.concurrent.PriorityBlockingQueue;
    
    /**
     * @author: Amy
     * @create: 2023-01-31 12:17
     **/
    public class Test2 {
        
        public static void main(String[] args) {
        
            int[]nums ={
        3,4,3,3};
            int k=2;
            System.out.println(Arrays.toString(maxSubsequence(nums, k)));
        }
        public static int[] maxSubsequence(int[] nums, int k) {
        
    
            PriorityQueue<Integer> pq=new PriorityQueue<>();//1.优先队列用于排序,list方便添加删除
            List<Integer> list=new ArrayList<>();
            for(int n:nums){
        //2.遍历，将nums的元素添加到队列和list
                pq.add(n);
                list.add(n);
            }
    
            int[] ans=new int[k];//3.定义ans的数组，长度为k
    
            for(int i=0;i<nums.length-k;i++)
                //4.nums的长度减去k的长度也就是说需要取出的元素个数，pq已经排序的数据，删除队列头元素，并删除list的元素，也就是最后符合要求的元素
                list.remove(pq.remove());
    
            for(int i=0;i<k;i++)
                //5.获得list元素并放入数组ans中
                ans[i]=list.get(i);
    
            return ans;//6.返回ans数组
        }
    }

[4, 3]

## 代码2： ##

public int[] maxSubsequence(int[] nums, int k) {
        
            PriorityQueue<Integer> pq = new PriorityQueue<>(k + 1);
            for (int n : nums) {
        
                pq.offer(n);
                if (pq.size() > k) {
        
                    pq.poll();
                }
            }
            Map<Integer, Integer> freq = new HashMap<>();
            for (int n : pq) {
        
                freq.merge(n, 1, Integer::sum);
            }
            int[] seq = new int[k]; 
            int i = 0;
            for (int n : nums) {
        
                if (freq.merge(n, -1, Integer::sum) >= 0) {
        
                    seq[i++] = n;
                }
            }
            return seq;
        }

## 代码3： ##

class Node{
        
        int index,value;
        Node(int index,int value){
        
            this.index=index;
            this.value=value;
        }
    }
    
    class Solution {
        
        public int[] maxSubsequence(int[] nums, int k) {
        
            Node nodes[]=new Node[nums.length];
            for(int i=0;i<nums.length;i++)
                nodes[i]=new Node(i,nums[i]);
            Arrays.sort(nodes,(a,b)->a.value-b.value);
            Arrays.sort(nodes,nums.length-k,nums.length,(a,b)->a.index-b.index);
            int res[]=new int[k];
            for(int i=0;i<k;i++)
                res[k-1-i]=nodes[nums.length-1-i].value;
            return res;
        }
    }