首页 > 编程学习 > 【leetcode】和最小的 k 个数对

【leetcode】和最小的 k 个数对

发布时间:2022/10/5 15:41:01

0、参考资料

优先级队列的使用:https://blog.csdn.net/weixin_44627672/article/details/127160367

Array数组排序:最多可参加会议的个数

集合排序的例子:最小时间差

集合之间的互转以及Array.sort:Array与Set互转

一、题目描述

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

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

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

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

二、代码思路

暴力完全可以解决 把所有情况都列举出来
然后从这些数组中选出前k个最小的

难点:每个数组对应一个值,也就是数组为key 数组数字和为 value。

如果使用TreeMap key值显然会重复,但是比较器我们可以使用(a,b) -> a[0]+a[1] -(b[0]+b[1]) 来比较value

如果是使用优先级队列呢 ?

使用最大优先级队列,最终保持优先级队列大小为k,同样可以使用比较器来维护优先级。也可以处理二维数组,也不存在key重复的问题。

但是如果全放入优先级队列暴力时间复杂度到o(m*n)

所以,其中一种优化方法就是减少放入优先级队列的元素。

代码题解

package leetcode;import org.junit.jupiter.api.Test;import java.util.*;/** @author lzy* @version 1.0* */
public class kSmallestPairs {public static void main(String[] args) {int arr[] = {1,7,11};int arr2[] = {2,4,6};kSmallestPairs(arr,arr2,3);}public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {//暴力完全可以解决 把所有情况都列举出来//然后从这些数组中选出前k个最小的//难点:每个数组对应一个值,也就是数组为key 数组数字和为 value//如果使用TreeMap key值显然会重复,但是比较器我们可以使用(a,b) -> a[0]+a[1] -(b[0]+b[1]) 来比较value//如果是使用优先级队列呢 ? 使用最大优先级队列,最终保持优先级队列大小为k//但是暴力时间复杂度到o(m*n)int array[][] = new int[nums1.length * nums2.length][2];int j = 0;for (int i = 0; i < nums1.length; i++) {for (int item : nums2) {array[j++] = new int[]{nums1[i], item};}}PriorityQueue<int[]> queue = new PriorityQueue(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return (o2[0] + o2[1]) - (o1[0] + o1[1]);}});for (int i = 0; i < array.length; i++) {queue.offer(array[i]);if (queue.size() > k) {queue.poll();}}List<List<Integer>> res = new ArrayList<>();for (int i = queue.size() - 1; i >= 0; i--) {int [] arr = queue.poll();//有个疑问,为什么数组转不成list ? 已解决/*int arr1[] = new int[]{1, 2};List<int[]> ints = Arrays.asList(arr1);*/List<Integer> list = new ArrayList<>();list.add(arr[0]);list.add(arr[1]);res.add(list);}return res;}//数组排序//我们可以使用Arrays.sort对一维数组进行排序,也可以对二维数组进行排序,也可以对对象数组进行排序//同理,我们也可以使用Collection.sort 对集合进行排序@Testpublic void arraySort() {Arrays.sort(new int[]{3,2,1});int arr[][] = new int[3][3];for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {arr[i][j] = i + j;}}Arrays.sort(arr, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] + o1[1] - o2[1] - o2[0];}});System.out.println(Arrays.toString(arr[0]));}//对集合进行排序public void collectionSort() {List<Integer> list = new ArrayList<>();Collections.sort(list, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});}/** @Desc: 集合之间的互转* */@Testpublic void convertCollection() {String[] s = new String[]{"A", "B", "C", "D","E"};List<String> strings = Arrays.asList(s);//我们可以使用Array.asList 将数组转成集合,但是这个list集合并不能add,自然并不能扩容,就可以理解为数组。//注意要声明为整型数组,否则可能将类型T 默认赋值为int[],而不会转成整形集合。Integer arr[] = {1,2,3};List<Integer> list = Arrays.asList(arr);int arr1[] = {1,2,3};List<int[]> ints = Arrays.asList(arr1);System.out.println(Arrays.toString(ints.get(0)));/** 2、set 转 list* Set 和 list 集合的构造函数中都有相应的转换* 其底层就是.toArray,然后使用copyof 对数组进行复制,其中应该还会对数组的类型进行判断。* */HashSet<Integer> integers = new HashSet<>(list);ArrayList<Integer> integers1 = new ArrayList<>(integers);HashMap<Integer, Integer> integerHashMap = new HashMap<>();Collection<Integer> values = integerHashMap.values();ArrayList<Integer> integers2 = new ArrayList<>(values);HashSet<Integer> integers3 = new HashSet<>(values);/** 3、Array和Set互转* 其实本质是Array.asList 转成集合 也就是使用静态内部类 new Arraylist* 以及 Collection.toArray转成数组 底层必然是 for each 遍历集合,赋值数组* *///相当于传入一个泛型,T为整形,所以生成整形数组Integer[] integers4 = integers.toArray(new Integer[0]);}
}

本文链接:https://www.ngui.cc/article/show-564808.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000