查找和最小的K对数字

主函数里边是测试数据,中间死在了num5和num6,后来查了查是因为排序有bug，所以改掉了注释的判断条件必须有==返回0

主要就是暴力解决,写了俩小时,吐了

先给出答案,然后是我写的测试的全部代码,可以直接运行:

解题代码

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> reliList = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0) return reliList;// 不能返回null,必须先声明,所以在这

                if(k <= 0)return reliList;
        int[][] arr = new int[nums1.length * nums2.length][2];//暴力的数组
        int count = 0;

        for (int i = 0; i < nums1.length; ++i) {// 暴力

            for (int j = 0; j < nums2.length; ++j) {

                arr[count][0] = nums1[i];
                arr[count++][1] = nums2[j];

            }

        }

        Comparator<int[]> cmp = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if((o1[0] + o1[1]) > (o2[0] + o2[1])){
                    return 1;
                }else if((o1[0] + o1[1]) == (o2[0] + o2[1])) {
                    return 0;
                }else {
                    return -1;
                }
                //return (o1[0] + o1[1]) >= o2[0] + o2[1] ? 1 : -1;// 不能用这个做判断条件,排序Arrays.sort算法有bug
            }

        };
        Arrays.sort(arr, cmp);


        for (int i = 0; i < arr.length && reliList.size() < k; ++i) {
            List<Integer> newList = new ArrayList<Integer>();
            newList.add(arr[i][0]);
            newList.add(arr[i][1]);
            //System.out.println(arr[i][0]+" "+arr[i][1]);
            reliList.add(newList);
        }

        return reliList;
    }

全部调试代码

package st;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Min_K {
    public static void main(String[] args) {
        Min_K min_K = new Min_K();
        int[] num1 = { 1, 7, 11 };
        int[] num2 = { 2, 4, 6 };
        int[] num3 = { 1, 1, 2 };
        int[] num4 = { 1, 2, 3 };
        int[] num5 =
        {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
        int[] num6 =
        {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

        List<List<Integer>> newlistList = min_K.kSmallestPairs(num1, num2, 3);
        List<List<Integer>> newlistList2 = min_K.kSmallestPairs(num3, num4, 2);
        System.out.println();
        System.out.println();
         List<List<Integer>> newlistList3 = min_K.kSmallestPairs(num5,num6,1000);

    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> reliList = new ArrayList<>();// 不能返回null
        if (nums1.length == 0 || nums2.length == 0)
            return reliList;
        if (k <= 0)
            return reliList;
        int[][] arr = new int[nums1.length * nums2.length][2];//
        int count = 0;

        for (int i = 0; i < nums1.length; ++i) {// 暴力
            for (int j = 0; j < nums2.length; ++j) {
                arr[count][0] = nums1[i];
                arr[count++][1] = nums2[j];
            }
        }

        Comparator<int[]> cmp = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // TODO Auto-generated method stub
                if((o1[0] + o1[1]) > (o2[0] + o2[1])){
                    return 1;
                }else if((o1[0] + o1[1]) == (o2[0] + o2[1])) {
                    return 0;
                }else {
                    return -1;
                }
                //return (o1[0] + o1[1]) >= o2[0] + o2[1] ? 1 : -1;// 不能用这个,排序Arrays.sort算法有bug
            }

        };
        Arrays.sort(arr, cmp);
        /*
         * System.out.println("sort~~~~~~"); for(int i=0;i<arr.length;++i) {
         * System.out.println(arr[i][0]+" "+arr[i][1]); }
         * 
         * 
         * System.out.println("k~~~~~~");
         */

        for (int i = 0; i < arr.length && reliList.size() < k; ++i) {
            List<Integer> newList = new ArrayList<Integer>();
            newList.add(arr[i][0]);
            newList.add(arr[i][1]);
            //System.out.println(arr[i][0]+" "+arr[i][1]);
            reliList.add(newList);
        }

        return reliList;
    }
}