rahman.kdd
BAN USERNo upper bond is not problem, for limited memory we can try to reduce the stream by getting rid of unwanted part.
i can get the middle element by going through the numbers, then make it the pivot and do quick sort, get rid of first half of the numbers. each time we keep track of how many numbers did we throw away.
when the amount of numbers is small enough follow your algorithm
I've jus ACed the same problem in leetcode.
Here is my code:
public class Solution {
public int singleNumber(int[] A) {
if(A.length <1) return 0;
int result = 0;
int count = 0; //adding binary digits at the same place
for(int j = 0; j < 32; j++){
for(int i = 0; i < A.length; i++){
if(((A[i] >> j) & 1) == 1)
count++;
}
result |= ((count % 3) << j); //this gives binary digit of the single one at Jth place.
count = 0;
}
return result;
}
}
Basically used the top answer strategy, adding numbers up bitwise, mod 3 get the bit for the single one.
Time complexity O(n), space complexity O(1);
RepEileenBaker, Applications Developer at ABC TECH SUPPORT
I am an experienced and dedicated professional with a track record of effective mentorship. Nowaday most people search for Ambani ...
I love this answer
- rahman.kdd November 12, 2014