|
28 | 28 |
|
29 | 29 | */ |
30 | 30 | publicclass_632 { |
31 | | -/** |
32 | | - * reference: https://discuss.leetcode.com/topic/94445/java-code-using-priorityqueue-similar-to-merge-k-array/2 |
33 | | - */ |
34 | | -publicint[]smallestRange(List<List<Integer>>nums) { |
35 | | -PriorityQueue<int[]>minHeap =newPriorityQueue<>(nums.size(), (a,b) ->a[0] -b[0]); |
36 | | -/**int[] array consists of three numbers: value; which list in nums; index of value in this list*/ |
| 31 | +publicstaticclassSolution1 { |
| 32 | +/** |
| 33 | + * reference: https://discuss.leetcode.com/topic/94445/java-code-using-priorityqueue-similar-to-merge-k-array/2 |
| 34 | + */ |
| 35 | +publicint[]smallestRange(List<List<Integer>>nums) { |
| 36 | +PriorityQueue<int[]>minHeap =newPriorityQueue<>(nums.size(), (a,b) ->a[0] -b[0]); |
| 37 | +/**int[] array consists of three numbers: value; which list in nums; index of value in this list*/ |
37 | 38 |
|
38 | | -intmax =nums.get(0).get(0); |
39 | | -for (inti =0;i <nums.size();i++) { |
40 | | -minHeap.offer(newint[]{nums.get(i).get(0),i,0}); |
41 | | -max =Math.max(max,nums.get(i).get(0)); |
42 | | - } |
43 | | -intminRange =Integer.MAX_VALUE; |
44 | | -intstart = -1; |
45 | | -while (minHeap.size() ==nums.size()) { |
46 | | -int[]curr =minHeap.poll(); |
47 | | -if (max -curr[0] <minRange) { |
48 | | -minRange =max -curr[0]; |
49 | | -start =curr[0]; |
| 39 | +intmax =nums.get(0).get(0); |
| 40 | +for (inti =0;i <nums.size();i++) { |
| 41 | +minHeap.offer(newint[]{nums.get(i).get(0),i,0}); |
| 42 | +max =Math.max(max,nums.get(i).get(0)); |
50 | 43 | } |
51 | | -if (curr[2] +1 <nums.get(curr[1]).size()) { |
52 | | -curr[0] =nums.get(curr[1]).get(curr[2] +1); |
53 | | -curr[2]++; |
54 | | -minHeap.offer(curr); |
55 | | -max =Math.max(max,curr[0]); |
| 44 | +intminRange =Integer.MAX_VALUE; |
| 45 | +intstart = -1; |
| 46 | +while (minHeap.size() ==nums.size()) { |
| 47 | +int[]curr =minHeap.poll(); |
| 48 | +if (max -curr[0] <minRange) { |
| 49 | +minRange =max -curr[0]; |
| 50 | +start =curr[0]; |
| 51 | + } |
| 52 | +if (curr[2] +1 <nums.get(curr[1]).size()) { |
| 53 | +curr[0] =nums.get(curr[1]).get(curr[2] +1); |
| 54 | +curr[2]++; |
| 55 | +minHeap.offer(curr); |
| 56 | +max =Math.max(max,curr[0]); |
| 57 | + } |
56 | 58 | } |
| 59 | +returnnewint[]{start,start +minRange}; |
57 | 60 | } |
58 | | -returnnewint[]{start,start +minRange}; |
59 | 61 | } |
60 | 62 | } |