632.Smallest-Range-Covering-Elements-from-K-Lists

632. Smallest Range Covering Elements from K Lists

题目地址

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

题目描述

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:
Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:
The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.

代码

Approach #1 Priority Queue + Next Array

Time: O(n * log m) && Space: O(m)

class Solution {
  public int[] smallestRange(int[][] nums) {
        int minx = 0;
    int miny = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    int[] next = new int[nums.length];
    boolean flag = true;
    PriorityQueue<Integer> min_queue = new PriorityQueue<Integer>((i, j) -> nums[i][next[i]] - nums[j][next[j]]);
    for (int i = 0; i < nums.length; i++) {
      min_queue.offer(i);
      max = Math.max(max, nums[i][0]);
    }
    for (int i = 0; i < nums.length && flag; i++) {
      for (int j = 0; j < nums[i].length && flag; j++) {
        int min_i = min_queue.poll();
        if (max - nums[min_i][next[min_i]] < miny - minx) {
          minx = nums[min_i][next[min_i]];
          miny = max;
        }
        next[min_i]++;
        if (next[min_i] == nums[min_i].length) {
          flag = false;
          break;
        }
        min_queue.offer(min_i);
        max = Math.max(max, nums[min_i][next[min_i]]);
      }
    }
    return new int[] {minx, miny};
  }
}

Approach #2 Two Pointer [TLE]

Time complexity : O(nm) Space complexity : O(m)

next[i] refers to the element which needs to be considered next in the (i-1)th list.

class Solution {
  public int[] smallestRange(int[][] nums) {
    int minx = 0;
    int miny = Integer.MAX_VALUE;
    int[] next = new int[nums.length];
    boolean flag = true;
    for (int i = 0; i < nums.length && flag; i++) {
      for (int j = 0; j < nums[i].length && flag; j++) {
        int min_i = 0;
        int max_i = 0;
        for (int k = 0; k < nums.length; k++) {
          if (nums[k][next[k]] < nums[min_i][next[min_i]]) {
            min_i = k;
          }
          if (nums[k][next[k]] > nums[max_i][next[max_i]]) {
            max_i = k;
          }
        }
        if (nums[max_i][next[max_i]] - nums[min_i][next[min_i]] < miny - minx) {
          minx = nums[min_i][next[min_i]];
          miny = nums[max_i][next[max_i]];
        }
        next[min_i]++;
        if (next[min_i] == nums[min_i].length) {
          flag = false;
        }
      }
    }
    return new int[] {minx, miny};
  }
}

Approach #3 maxHeap & minHeap

class Solution {
  public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> min = new PriorityQueue<>(1, new Comparator<int[]>(){
      public int compare(int[] n1, int[] n2) {
        return nums.get(n1[0]).get(n1[1]) - nums.get(n2[0]).get(n2[1]);
      }
    });

   // PriorityQueue<int[]> min = new PriorityQueue<>((n1, n2) -> nums.get(n1[0]).get(n1[1]) - nums.get(n2[0]).get(n2[1]));

    PriorityQueue<int[]> max = new PriorityQueue<>(1, new Comparator<int[]>() {
      public int compare(int[] n1, int[] n2) {
        return nums.get(n2[0]).get(n2[1]) - nums.get(n1[0]).get(n1[1]);
      }
    });

    for (int i = 0; i < nums.size(); i++) {
      int[] tmp = new int[]{i, 0}; // index -> next index
      min.offer(tmp);
      max.offer(tmp);
    }
    int[] res = new int[] {Integer.MIN_VALUE, Integer.MAX_VALUE};

    while (min.size() == nums.size()) {
      int[] m1 = max.peek();
      int[] m2 = min.poll();
      if ((long)nums.get(m1[0]).get(m1[1]) - (long)nums.get(m2[0]).get(m2[1]) < (long)res[1] - (long)res[0]) {
        res[0] = nums.get(m2[0]).get(m2[1]);
        res[1] = nums.get(m1[0]).get(m1[1]);
      }

      if (m2[1] + 1 < nums.get(m2[0]).size()) {
        int[] m3 = new int[]{m2[0], m2[1] + 1};
        min.offer(m3);
        max.offer(m3);
        max.remove(m2);
      }
    }

    return res;
  }
}