BiruLyu
7/17/2017 - 9:32 PM

## 632. Smallest Range(#).java

``````public class Solution {
public int[] smallestRange(int[][] nums) {
int minx = 0, 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, max_i = 0;
for (int k = 0; k < nums.length; k++) {
if (nums[min_i][next[min_i]] > nums[k][next[k]])
min_i = k;
if (nums[max_i][next[max_i]] < nums[k][next[k]])
max_i = k;
}
if (miny - minx > nums[max_i][next[max_i]] - nums[min_i][next[min_i]]) {
miny = nums[max_i][next[max_i]];
minx = nums[min_i][next[min_i]];
}
next[min_i]++;
if (next[min_i] == nums[min_i].length) {
flag = false;
}
}
}
return new int[] {minx, miny};
}
}``````
``````public class Solution {
class Element{
int val,idx,row;
Element(int val,int idx, int row){
this.val=val;
this.idx=idx;
this.row=row;
}
}
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Element> pq= new PriorityQueue<Element>(new Comparator<Element>(){
public int compare(Element a,Element b){
return a.val-b.val;
}
});
int max=Integer.MIN_VALUE;
int range=Integer.MAX_VALUE;
int start=-1;
int end=-1;
for(int i=0; i< nums.size();i++){
Element e = new Element(nums.get(i).get(0),0,i);
pq.offer(e);
max=Math.max(e.val,max);
}
while(pq.size()==nums.size()){
Element cur=pq.poll();
if(max-cur.val<range){
range=max-cur.val;
start=cur.val;
end=max;
}
if(cur.idx+1<nums.get(cur.row).size()){
cur.idx=cur.idx+1;
cur.val=nums.get(cur.row).get(cur.idx);
pq.offer(cur);
max=Math.max(cur.val,max);
}
}
return new int[]{start,end};
}
}``````
``````public class Solution {
public int[] smallestRange(List<List<Integer>> nums) {

PriorityQueue<Element> pq = new PriorityQueue<Element>(new Comparator<Element>() {
public int compare(Element a, Element b) {
return a.val - b.val;
}
});
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) {
Element e = new Element(i, 0, nums.get(i).get(0));
pq.offer(e);
max = Math.max(max, nums.get(i).get(0));
}
int range = Integer.MAX_VALUE;
int start = -1, end = -1;
while (pq.size() == nums.size()) {

Element curr = pq.poll();
if (max - curr.val < range) {
range = max - curr.val;
start = curr.val;
end = max;
}
if (curr.idx + 1 < nums.get(curr.row).size()) {
curr.idx = curr.idx + 1;
curr.val = nums.get(curr.row).get(curr.idx);
pq.offer(curr);
if (curr.val > max) {
max = curr.val;
}
}
}

return new int[] { start, end };
}

class Element {
int val;
int idx;
int row;

public Element(int r, int i, int v) {
val = v;
idx = i;
row = r;
}
}
}

``````