【leetcode】和最小的 k 个数对
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[]>() {
@Override
public 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 对集合进行排序
@Test
public 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[]>() {
@Override
public 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>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
}
/*
* @Desc: 集合之间的互转
* */
@Test
public 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]);
}
}