632 Smallest Range

632. Smallest Range​
1. Question
You haveklists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of theklists.
We define the range [a,b] is smaller than range [c,d] ifb-a < d-cora < cifb-a == d-c.
Example 1:
1
Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
2
​
3
Output: [20,24]
4
​
5
Explanation:
6
​
7
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
8
List 2: [0, 9, 12, 20], 20 is in range [20,24].
9
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Copied!
Note:
1.The given list may contain duplicates, so ascending order means >= here.
2.1 <=k<= 3500
3.-10^5 <=value of elements<= 10^5.
2. Implementation
(1) Two Pointers + HashMap
思路：这题可以转换成Minimum Size Substring来做，首先建立一个list存储每个数和这个数所在的list的id，然后按照数的大小对list排序。接下来的做法就和Minimum Size Substring一样，维护一个Sliding Window,当这个window包含所有list的id时，则更新start pointer,结果即可
1
class Solution {
2
    public int[] smallestRange(List<List<Integer>> nums) {
3
        int n = nums.size();
4
        int[] map = new int[n];
5
        List<NumInfo> list = new ArrayList<>();
6
        int[] res = new int[2];
7
​
8
        for (int i = 0; i < n; i++) {
9
            for (int num : nums.get(i)) {
10
                list.add(new NumInfo(num, i));
11
            }
12
        }
13
​
14
        Collections.sort(list);
15
​
16
        int size = list.size();
17
        int diff = Integer.MAX_VALUE;
18
        int count = 0;
19
​
20
        for (int start = 0, end = 0; end < size; end++) {
21
            if (map[list.get(end).id] == 0) {
22
                ++count;
23
            }
24
            ++map[list.get(end).id];
25
​
26
            while (count == n) {
27
                int curDiff = list.get(end).num - list.get(start).num;
28
                if (curDiff < diff) {
29
                    diff = curDiff;
30
                    res[0] = list.get(start).num;
31
                    res[1] = list.get(end).num;
32
                }
33
​
34
                if (map[list.get(start).id] == 1) {
35
                    --count;
36
                }
37
                --map[list.get(start).id];
38
                ++start;
39
            }
40
        }
41
        return res;
42
    }
43
​
44
    class NumInfo implements Comparable<NumInfo> {
45
        int num, id;
46
​
47
        public NumInfo(int num, int id) {
48
            this.num = num;
49
            this.id = id;
50
        }
51
​
52
        public int compareTo(NumInfo that) {
53
            return this.num - that.num;
54
        }
55
    }
56
}
Copied!
(2) Heap
1
class Solution {
2
    public int[] smallestRange(List<List<Integer>> nums) {
3
        PriorityQueue<Element> minHeap = new PriorityQueue<>();
4
​
5
        int n = nums.size();
6
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
7
​
8
        for (int i = 0; i < n; i++) {
9
            minHeap.add(new Element(i, 0, nums.get(i).get(0)));
10
            max = Math.max(max, nums.get(i).get(0));
11
        }
12
​
13
        int range = Integer.MAX_VALUE;
14
        int start = -1, end = -1;
15
​
16
        while (minHeap.size() == n) {
17
            Element curNum = minHeap.remove();
18
​
19
            if (max - curNum.val  < range) {
20
                range = max - curNum.val;
21
                start = curNum.val;
22
                end = max;
23
            }
24
​
25
            if (curNum.index + 1 < nums.get(curNum.row).size()) {
26
                int nextNum = nums.get(curNum.row).get(curNum.index + 1);
27
                minHeap.add(new Element(curNum.row, curNum.index + 1, nextNum));
28
                max = Math.max(max, nextNum);
29
            }
30
        }
31
        return new int[] {start, end};
32
    }
33
​
34
    class Element implements Comparable<Element> {
35
        int row, index, val;
36
​
37
        public Element(int row, int index, int val) {
38
            this.row = row;
39
            this.index = index;
40
            this.val = val;
41
        }
42
​
43
        public int compareTo(Element that) {
44
            return this.val - that.val;
45
        }
46
    }
47
}
Copied!
3. Time & Space Complexity
Two Pointers + HashMap: 时间复杂度O(nlogn), 空间复杂度O(nk), n为nums的size， k为每个nums的平均元素个数
Heap: 时间复杂度O(nklogn), 空间复杂度O(n)

611 Valid Triangle Number

713 Subarray Product Less Than K

Last modified 2yr ago

Copy link

Contents

632. Smallest Range

1. Question

2. Implementation

3. Time & Space Complexity

632. Smallest Range​

1. Question

2. Implementation

3. Time & Space Complexity

632. Smallest Range