两个数组的元素之和最大的前k项

题目描述：

---

解决思路：

• 时间复杂度很低，除了数组排序那块需要O(NlogN)（或者O(MlogM)，看谁最大）之外，后面的顶多需要O(k^2)，应该不是很大。
• 然后其实有O(N)的解法，链接如下：https://blog.csdn.net/huntzw/article/details/25157743

import java.util.*;

public class Main {
    //2,4,2,7,7-3,2,5,6,1,9:6
    //16 16 13 13 13 11

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] tem = line.split("-");
        String[] array1 = tem[0].split(",");
        String[] temp = tem[1].split(":");
        String[] array2 = temp[0].split(",");
        int K = Integer.parseInt(temp[1]);
        Arrays.sort(array1, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        Arrays.sort(array2, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        int[] arr_1 = new int[array1.length];
        int[] arr_2 = new int[array2.length];
        for(int i = 0; i < array1.length; i++){
            arr_1[i] = Integer.parseInt(array1[i]);
        }
        for(int i = 0; i < array2.length; i++){
            arr_2[i] = Integer.parseInt(array2[i]);
        }
        ArrayList<Integer> sum = new ArrayList<>();
        int num_1 = K > arr_1.length ? arr_1.length : K;
        int num_2 = K > arr_2.length ? arr_2.length : K;
        for(int i = 0; i < num_1; i++){
            for(int j = 0; j < num_2; j++){
                sum.add(arr_1[i] + arr_2[j]);
            }
        }
        Collections.sort(sum, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int i = 0; i < K; i++)
            System.out.println(sum.get(i));
    }
}