【LeetCode】找到和最大的长度为 K 的子序列 java

【LeetCode】找到和最大的长度为 K 的子序列 java 题目

给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大 。

请你返回 任意 一个长度为 k 的整数子序列。

子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。

示例 1：

输入：nums = [2,1,3,3], k = 2
输出：[3,3]
解释：
子序列有最大和：3 + 3 = 6 。
示例 2：

输入：nums = [-1,-2,3,4], k = 3
输出：[-1,3,4]
解释：
子序列有最大和：-1 + 3 + 4 = 6 。
示例 3：

输入：nums = [3,4,3,3], k = 2
输出：[3,4]
解释：
子序列有最大和：3 + 4 = 7 。
另一个可行的子序列为 [4, 3] 。

题解

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        PriorityQueue queue = new PriorityQueue<>((a,b)-> b[1] - a[1]);
        int[][] temArr = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            temArr[i][0] = i;
            temArr[i][1] = nums[i];
        }
        // 按照数值nums[idx]从大到小排序
        Arrays.sort(temArr,(a,b)-> b[1] - a[1]);
        // 按照索引idx从小到大（前K个）进行排列
        Arrays.sort(temArr,0, k, Comparator.comparingInt(a -> a[0]));

        // 复制结果
        int[] res = new int[k];
        for(int idx = 0; idx < k; idx++){
            res[idx] = temArr[idx][1];
        }
        return res;
    }
}

知识点

Arrays.sort() 重载了四类方法

sort(T[] a)：对指定T型数组按数字升序排序。

int[] ints = new int[]{12, 4, 6, 7, 2, 8, 3, 9};// 按 数字
char[] chars = new char[]{'a', 'c', 'b', 'i', '+'};// 按 ascii 码
byte[] bytes = new byte[]{7, 5, 6, 10, -1};// 按 字节数
Arrays.sort(ints);
Arrays.sort(chars);
Arrays.sort(bytes);
System.out.println(Arrays.toString(ints));
// 结果 ：[2, 3, 4, 6, 7, 8, 9, 12]
System.out.println(Arrays.toString(chars));
// 结果 ：[+, a, b, c, i]
System.out.println(Arrays.toString(bytes));
// 结果 ：[-1, 5, 6, 7, 10]

sort(T[] a,int formIndex, int toIndex)：对指定T型数组的指定范围按数字升序排序。

int[] ints = new int[]{12, 4, 6, 7, 2, 8, 3, 9};// 按 数字
char[] chars = new char[]{'a', 'c', 'b', 'i', '+'};// 按 ascii 码
byte[] bytes = new byte[]{7, 5, 6, 10, -1};// 按 字节数
Arrays.sort(ints, 2, 5);
Arrays.sort(chars, 2, 5);
Arrays.sort(bytes, 2, 5);
System.out.println(Arrays.toString(ints));
// 结果 ：[12, 4, 2, 6, 7, 8, 3, 9]
System.out.println(Arrays.toString(chars));
// 结果 ：[a, c, +, b, i]
System.out.println(Arrays.toString(bytes));
// 结果 ：[7, 5, -1, 6, 10]

sort(T[] a, Comparator c): 根据指定比较器产生的顺序对指定对象数组进行排序。

 
Integer[] ints = new Integer[]{12, 4, 6, 7, 2, 8, 3, 9};
Arrays.sort(ints, Collections.reverseOrder());
System.out.println(Arrays.toString(ints));
// 结果 ：[12, 9, 8, 7, 6, 4, 3, 2]

Arrays.sort(ints, new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});
// lambda 表达式
Arrays.sort(ints, (o1, o2) -> o2 - o1);

sort(T[] a, int formIndex, int toIndex, Comparator c): 根据指定比较器产生的顺序对指定对象数组的指定对象数组进行排序。

int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一
Arrays.sort(nums,new Comparator(){
    @Override
    public int compare(int[] a,int[] b){
        // 当第一维相等时比较第二维的
        if(a[0] == b[0]){
            return a[1]-b[1];
        }else{
            return a[0]-b[0];
        }
    }
});

// 方法二，使用 lambda 表达式
Arrays.sort(nums,(a,b) -> a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]);
for (int[] num : nums) {
    System.out.print(Arrays.toString(num));
}
// 结果 ： [1, 2][1, 3][3, 3][4, 5][5, 1]

int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一
Arrays.sort(nums,new Comparator(){
    @Override
    public int compare(int[] a,int[] b){
        // 当第二维相等时比较第一维的
        if(a[1] == b[1]){
            return a[0]-b[0];
        }else{
            return a[1]-b[1];
        }
    }
});

// 方法二，使用 lambda 表达式
Arrays.sort(nums,(a,b) -> a[1] == b[1]  ? a[0]-b[0] : a[1]-b[1]);
for (int[] num : nums) {
    System.out.print(Arrays.toString(num));
}
// 结果 ： [5, 1][1, 2][1, 3][3, 3][4, 5]

// 按第一维降序
if(a[0].equals(b[0]){
    return b[1]-a[1];
}else{
    return b[0]-a[0];
}
// 结果 ： [5, 1][4, 5][3, 3][1, 3][1, 2]