jayswami
BAN USERHere’s an explanation of my approach :
So let us say the 6 sorted arrays are:
2 10 20 25
1 5 6 7
23 24 25 26
5 6 7 8
24 28 50 52
3 21 51 53
initially we have 6 pointers on the 0th index of each array (2,1,23,5,24,3) <<
we find the interval of that set.. here it happens to be [1 24]
so range of {2,1,23,5,24,3} = [1 24]
we immediately remove the lowest element from the set, and insert the next element from that array.. in this case, 1.. w eincrement index of 2nd array.. next element is 5. So set becomes
{2,5,23,5,24,3} and range = [2 24] we replace the min_interval variable with [2 24] as 24-2 < 24-1
if we continue this, we get
2
1
23 [1 24] min = [1 24]
5
24
3
removeMin -> 1
2
5
23 [2 24] min = [2 24]
5
24
3
removeMin ->2
10
5
23 [3 24] min = [3 24]
5
24
3
removeMin ->3
10
5
23 [5 24] min = [5 24]
5
24
21
removeMin ->5
10
6
23 [5 24] min = [5 24]
5
24
21
removeMin ->5
10
6
23 [6 24] min = [6 24]
6
24
21
removeMin ->6
10
7
23 [6 24] min = [6 24]
6
24
21
removeMin -> 6
10
7
23 [7 24] min = [7 24]
7
24
21
after 2 time remove min 7
10
7 (last element)
23 [7 24] min = [7 24]
8
24
21
this is the terminating condition. the lower level cannot go above 7, and the max levels can only go up.. so [7 24] is the answer
new example
2 10 20 53
1 5 52 54
23 24 53 55
5 6 7 52
24 28 50 52
3 21 51 53
{(2,1,23,5,24,3), [1 24]} [1 24] -> {(2,5,23,5,24,3), [2 24]} [2 24] -> {(10,5,23,5,24,3), [3 24]} [3 24] -> {(10,5,23,5,24,21), [5 24]} [5 24]-> {(10,52,23,5,24,21), [5 24]}[5 24] ->{(10,52,23,6,24,21), [6 24]} [6 24]-> {(10,52,23,7,24,21), [7 24]}[7 24] ->{(10,52,23,52,24,21), [10 52]} [7 24] -> {(20,52,23,52,24,21), [20 52]}[7 24] ->{(53,52,23,52,24,21), [21 53]} [7 24] -> {(53,52,23,52,24,51), [23 53]}[7 24] -> {(53,52,24,52,24,51), [24 53]}[7 24] -> {(53,52,53,52,24,51), [24 53]}[7 24] -> (53,52,53,52,28,51), [28 53]}[7 24] -> (53,52,53,52,50,51),[50 53]}[50 53] -> (53,52,53,52,52,51),[51 53]}[51 53] -> (53,52,53,52,52,53),[52 53]}[52 53] -> (53,54,53,52,52,53),[52 54]}[52 53] ->
(53,54,54,52,52,53),[52 55]}[52 53] -> final solution [52 53]
Worst case running time = O(m * m* n)
can someone tell me what the average case running time would be? O (m*n) or O (n*mlgm) ?
worst case list of arrays would be m identical arrays.
public class ListOfArrays {
ArrayList<ArrayList<Integer>> listArray; // list of sorted arrays
ArrayList<Integer> minIndexList; // this list maintains the current index position within each array
int minArray;
boolean bFinal=false;
private class Interval {
Integer min= Integer.MAX_VALUE, max=Integer.MIN_VALUE;
boolean bFirst=true;
void setMinInterval() {
int low=Integer.MAX_VALUE,high=Integer.MIN_VALUE;
for(int i=0;i<minIndexList.size();i++) {
if(listArray.get(i).get(minIndexList.get(i))<low) {
low=listArray.get(i).get(minIndexList.get(i));
minArray=i;
}
if(listArray.get(i).get(minIndexList.get(i))>high) {
high=listArray.get(i).get(minIndexList.get(i));
}
}
if((bFirst==true) || ((long) (high-low)<(long) (max - min))){
min=low;
max=high;
bFirst=false;
}
}
public String toString() {
return String.format("[%d %d]", min, max);
}
}
ListOfArrays(ArrayList<ArrayList<Integer>> arrays) {
listArray=arrays;
}
/////////////////////
//
/////////////////////
private void removeMin() {
int i = minArray;
if(minIndexList.get(i)<listArray.get(i).size()-1) {
minIndexList.set(i, minIndexList.get(i)+1);
} else {
bFinal=true;
}
}
////////////////
//
////////////////
public Interval findMinRange() {
Interval v = new Interval();
minIndexList = new ArrayList<Integer>();
// init index list to 0th element
for(int i=0;i<listArray.size();i++){ minIndexList.add(0);}
v.setMinInterval();
while(bFinal!=true) {
removeMin();
v.setMinInterval();
}
return v;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
/*
2 10 20 53
1 5 52 54
23 24 53 55
5 6 7 152
24 28 50 152
3 21 51 53
*/
ArrayList<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a,b,c,d,e,f ;
a= new ArrayList<Integer>();
a.add(2);a.add(10);a.add(20);a.add(53);
b= new ArrayList<Integer>();
b.add(1);b.add(5);b.add(52);b.add(54);
c= new ArrayList<Integer>();
c.add(23);c.add(24);c.add(53);c.add(55);
d= new ArrayList<Integer>();
d.add(5);d.add(6);d.add(7);d.add(52);
e= new ArrayList<Integer>();
e.add(24);e.add(28);e.add(50);e.add(52);
f= new ArrayList<Integer>();
f.add(3);f.add(21);f.add(51);f.add(53);
arrays.add(a);arrays.add(b);arrays.add(c);
arrays.add(d);arrays.add(e);arrays.add(f);
ListOfArrays m = new ListOfArrays(arrays);
Interval v = m.findMinRange();
System.out.println("INPUT: "+arrays.toString());
System.out.println("OUTPUT: "+v.toString());
}
}
I am not very clear about the question.. especially with respect to the input , are we talking about levenshtein distance here? even then can you provide more clarity?
- jayswami March 04, 2014