amaniitm.gupta26
BAN USERRun Binary Search on first column until one row is left and then run Binary Search on that one row O(logr + logc) {r : number of rows, c : number of columns}
static private int BinarySearch(int[][] mat, int a, int rs, int cs, int ce){
if(cs > ce)
return -1;
int[] arr = mat[rs];
int mid = cs + (ce - cs)/2;
if(arr[mid] == a)
return 1;
if(arr[mid] > a)
return BinarySearch(mat, a, rs, cs, mid - 1);
else
return BinarySearch(mat, a, rs, mid + 1, ce);
}
static private int rec(int[][] mat, int a, int rs, int re, int cs, int ce){
if(rs > re)
return -1;
if(re - rs == 0)
return BinarySearch(mat, a, rs, cs, ce);
int rm = rs + (re - rs)/2 + 1;
if(mat[rm][0] == a)
return 1;
if(mat[rm][0] > a)
return rec(mat, a, rs, rm - 1, cs, ce);
else
return rec(mat, a, rm, re, cs, ce);
}
static public int bs2d(int[][] mat, int a){
int r = mat.length;
int c = mat[0].length;
if(r == 0 || c == 0)
return -1;
return rec(mat, a, 0, r - 1, 0, c - 1);
}
Using prefix delimiter as (length of string) + "#", Following is the code in Java:
static public String encode(ArrayList<String> al){
int l = al.size();
if(l == 0)
return "0#";
StringBuffer res = new StringBuffer();
for(String str: al){
int l1 = str.length();
res.append(l1 + "#" + str);
}
return res.toString();
}
static public ArrayList<String> decode(String a){
int l = a.length();
ArrayList<String> res = new ArrayList<String>();
int i = 0;
while(i < l){
int l1 = 0;
while(i < l && a.charAt(i) != '#'){
l1 = l1*10 + Character.getNumericValue(a.charAt(i));
i++;
}
res.add(a.substring(i + 1, i + 1 + l1));
i = i + 1 + l1;
}
return res;
}
RepGeraldRuder, Kindergarten teacher at Nelson Brothers
I am a kindergarten teacher who teaches basic written and reading skills to children. I make learning fun with numerous ...
RepCliftonMalone, Android Engineer at ABC TECH SUPPORT
Hello, I am a Seo Analyst with 5 years of experience in helping large ecommerce websites reach higher organic positions ...
RepNevaLucas, Analyst at Apache Design
I was the Training manager in Checker Auto Parts Center. My current research projects are about astrology, vashikaran health outcomes ...
Repmaryjcowell, Android Engineer at AMD
Hey I am information designer.Information Designers facilitate the delivery of information by translating complex information into information that users ...
RepPurserCaudle, Network Engineer at AppPerfect
Hi I am Purser, a scientific writer who is a journalist who researches and reports on news and trends in ...
With two pointer approach:
- amaniitm.gupta26 January 24, 2017