rit
BAN USER// Solution based on binary search approach. Time complexity O(log n)
public static void hIndex(int[] array) {
int length = array.length;
int h = hIndex(array, 0, length-1, 0);
System.out.print(h);
}
public static int hIndex(int[] array, int start, int end, int h) {
if(start > end)
return h;
int mid = (start+end)/2;
if(array[mid] >= array.length-mid)
return hIndex(array, start, mid-1, array.length-mid);
else
return hIndex(array, mid+1, end, h);
}
This is a O(n^2) solution. Algorithm goes as follows -
1. find the length of number we want to obtain i.e. count = length(string) - n
2. since, relative order of characters in string is not to be changed, we iterate from start (initially set to 0) to length(string) - (count-1) to find minimum value character(or the index of minimum value character in char array).
3. update the start to (min) index+1 for next iteration and reduce count by 1.
4. keep iterating till we have not found the number of characters required i.e. till count is not reduced to 0.
public static String GenerateLowestNumber(String number, int n) {
if(number == null || number .length() == 0 || n >= number.length())
return null;
int count = number.length() - n;
char[] num = number.toCharArray();
StringBuilder st = new StringBuilder();
int start = 0;
while(count > 0) {
int end = number.length() - count + 1;
int index = findMin(start, end, num);
start = index+1;
st.append(num[index]);
count--;
}
return st.toString();
}
public static int findMin(int start, int end, char[] number) {
if(start > end || number == null || number.length == 0)
return Integer.MIN_VALUE;
if(start == end)
return start;
int min = start;
for(int i = start; i <end; i++) {
if(number[min] > number[i])
min = i;
}
return min;
}
public class Node {
boolean endFlag;
Node[] childrens;
boolean isPrefixWord;
char value;
boolean isRoot;
public Node(boolean isRoot, char value) {
childrens = new Node[26];
endFlag = false;
isPrefixWord = false;
this.isRoot = isRoot;
this.value = value;
}
}
public class filterStrings {
public static void main(String args[]) {
Node root = new Node(true,'/');
addWord("/flapp/server/apache", root);
addWord("/d/apps", root);
addWord("/d/apps/pub", root);
addWord("/flapp", root);
addWord("/flocal/firms", root);
addWord("/d/sw/java", root);
addWord("/d/sw/orcl/jdbc", root);
StringBuilder str = new StringBuilder("/");
printTrie(root, str);
}
public static void addWord(String str, Node root) {
char c;
for(int i = 0; i < str.length(); i++ ) {
c = str.charAt(i);
if(c == '/') {
root.isPrefixWord = true;
continue;
}
if(root.childrens[c-'a'] == null) {
root.childrens[c-'a'] = new Node(false,c);
}
root = root.childrens[c-'a'];
if(root.endFlag) {
break;
}
}
root.endFlag = true;
root.isPrefixWord = false;
for(int i =0; i < 26; i++) {
root.childrens[i] = null;
}
}
public static void printTrie(Node root, StringBuilder str) {
if(root.endFlag) {
System.out.println(str);
return;
}
for(int i = 0; i < 26; i++) {
if(root.childrens[i] != null) {
str.append(root.childrens[i].value);
if(root.childrens[i].isPrefixWord)
str.append("/");
printTrie(root.childrens[i], str);
str.deleteCharAt(str.length()-1);
if(root.childrens[i].isPrefixWord)
str.deleteCharAt(str.length()-1);
}
}
}
}
public static int lastIndexVariantOfBinarySearch(int number, int[] array, int start, int end) {
if(end<start)
return -1;
int mid = (start+end)/2;
if(array[mid] == number && (mid == end || array[mid+1] != number))
return mid;
if(array[mid] <= number) {
return lastIndexVariantOfBinarySearch(number, array, mid+1, end);
}
else {
return lastIndexVariantOfBinarySearch(number, array, start, mid-1);
}
}
Referring to above solution, LBorder value may or may not be the top node of subtree having all the values less than x and similarly RBorder value may or may not be the top most node of subtree holding all values larger than y. Above algorithm will fail in this scenario.
Worst case complexity of this solution is O(n), but it may take much less time depending on tree structure.
- rit April 24, 2015