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

/**
 * 2种解法，1.优化后的暴力搜索
 * 2.优先队列
 */
public class _373 {
    //优化后的暴力搜索，每次循环找最小的
    static class Solution1 {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            int[] m2Idx = new int[nums1.length];
            List<List<Integer>> res = new ArrayList<>();
            int s = 0;
            while (res.size() < k) {
                int min = Integer.MAX_VALUE;
                int[] p = null;
                for (int i = s; i < m2Idx.length; i++) {
                    //相同条件下，可以直接跳过
                    if (i - 1 >= 0 && m2Idx[i - 1] == m2Idx[i]) {
                        continue;
                    }
                    if (m2Idx[i] == nums2.length) {
                        s++;
                        continue;
                    }
                    if (nums1[i] + nums2[m2Idx[i]] < min) {
                        p = new int[]{nums1[i], nums2[m2Idx[i]], i};
                        min = nums1[i] + nums2[m2Idx[i]];
                    }
                }
                if (p == null) break;
                m2Idx[p[2]]++;
                res.add(Arrays.asList(p[0], p[1]));
            }
            return res;
        }
    }
    static class Solution2{
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            //优先队列解法,与暴力求解思路类似，但是它获取最小值的时间复杂度为lgM;所以更快
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->{
                if(nums1[a[0]] + nums2[a[1]] == nums1[b[0]] + nums2[b[1]]){
                    return a[0] - b[0];
                }
                return nums1[a[0]] + nums2[a[1]] - (nums1[b[0]] + nums2[b[1]]);
            });
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0;i < nums1.length;i++){
                pq.offer(new int[]{i,0});
            }
            while(!pq.isEmpty() && k-- > 0){
                int[] cur = pq.poll();
                if(cur[1]+1 < nums2.length){
                    pq.offer(new int[]{cur[0],cur[1]+1});
                }
                res.add(Arrays.asList(nums1[cur[0]],nums2[cur[1]]));
            }
            return res;
        }
    }
}