LeetCode – Encuentre K pares con las sumas más pequeñas (Java)

Se le dan dos matrices de enteros nums1 y nums2 ordenados en orden ascendente y un entero k.

Defina un par (u, v) que consta de un elemento de la primera matriz y un elemento de la segunda matriz.

Encuentre los k pares (u1, v1), (u2, v2) … (uk, vk) con las sumas más pequeñas.

Ejemplo:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Solución Java

Este problema es similar al Super Ugly Number. La idea básica es usar una matriz para rastrear el índice del siguiente elemento en la otra matriz.

La mejor manera de entender esta solución es usando un ejemplo como nums1 = {1,3,11} y nums2 = {2,4,8}.

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    int total=nums1.length*nums2.length;
    if(total<k){
        k=total;
    }
 
    List<int[]> result = new ArrayList<int[]>();
    int[] idx = new int[nums1.length];//track each element's cursor in nums2
    while(k>0){
        int min=Integer.MAX_VALUE;
        int minIdx=-1;
        for(int i=0; i<nums1.length; i++){
            if(idx[i]<nums2.length && nums1[i]+nums2[idx[i]]<min){
                minIdx=i;
                min=nums1[i]+nums2[idx[i]];
            }
        }
        result.add(new int[]{nums1[minIdx],nums2[idx[minIdx]]});
        idx[minIdx]++;
        k--;
    }
 
    return result;
}