dharmendra
BAN USERConsidering the solution for small case characters only:
Another solution to this would be:
1) create an array A of dimension 2*26.
2) create another array B of dimension 26 and initialize by -1;
traverse through the given array of characters and for each encounter of a character x check in B's index x - 'a' if the value v is not -1. Check A[v] and increase it by 1.
Traverse through A and the first 1 in the value will be the first unique character.
public static void findUnique(char[] a) {
int[] A = new int[26];
int[] B = new int[26];
int elementsInA = 0;
int index = 0;
for (int i = 0; i < 26; i++)
B[i] = -1;
for (int i = 0; i < a.length; i++) {
index = B[a[i] - 'a'];
if (index != -1) {
A[index] += 1;
} else {
B[a[i] - 'a'] = elementsInA++;
A[B[a[i] - 'a']] = 1;
}
}
int foundAt = -1;
for(int i = 0 ; i < A.length ; i++){
if(A[i] == 1){
foundAt = i;
break;
}
}
if(foundAt == -1)
System.out.println("No unique");
else{
for(int i = 0 ; i < B.length ; i++){
if(B[i] == foundAt){
System.out.println((char)(i+'a'));
break;
}
}
}
}
this is not working for a,b,a,u,c,b
- dharmendra June 07, 2012nice solution. really appreciate this approach.
- dharmendra June 07, 2012:) The order of the function doesn't matter. If there is a main function with signature public static void main (String []args) in a public class. No matter where it appears in the lexicographic order in the code. That is the first function to be invoked by the JVM.
Moreover if you see two main functions with this signature then you are in trouble, It must give a compilation error saying duplicate methods.
I guess this only needs O(nm) time and no extra space. Isn't it obvious this has to be the element which falls on the intersection of an all zero row and an all zero column?
If you want explanation: What exactly is happening in this situation if a position i,j has a 1 then the ith row and the jth column is transformed to all 1s.
So which element will be untouched? The one which lies in the all zero rows and all zero columns. Hence the one at the intersection.
Hi, this solution prints First unique element is null. I believe it will not work in situations if there are three occurrences of a character.
- dharmendra June 02, 2012public static void test() {
char[] a = new char[] { 'a', 'a', 'b', 'q', 'b' };
LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<Character, Integer>();
for (int i = 0; i < a.length; i++) {
Character c = a[i];
int n = 0;
if (lhm.containsKey(c)) {
n = lhm.get(a[i]);
}
lhm.put(a[i], n + 1);
}
for (Entry<Character, Integer> e : lhm.entrySet()) {
if ((Integer) e.getValue() == 1) {
System.out.println(e.getKey());
break;
}
}
}
Is it really about two large integers or two large numbers? If it is integers we do not need strings to hold them. Moreover if it is for numbers then its easier.
- dharmendra June 08, 2012Steps:
Read each line from file A and store the number in form of String in a HashSet ( I will prefer a caching mechanism or multiple HashSets of sqrt(n) size). This will take care of duplicates in the same file.
After the first file is completely read and stored in the HashSets. Read the second file and use the Boyre Moore algorithm to search the strings from the second file against the HashSets.
If a hit is found in any of the sets then write the String in third file.
Analysis: Reading and storing into HashSets will take O(N) time and comparing in worst case take O(N) time where you have to compare to each element.
We need to analyze the Boyre Moore Algorithms complexity too where if the Strings to compare are almost of same length. In this case if there is a mismatch to occur in average case it will take O (L/10) where L is the length of the String and 10 is the base of numbers.