What I can think of is:
Algo:
Can you guys think of solution better than this. With O(n) runtime and using no extra space
An answer in Ruby, assuming one singleton, and all others exactly two appearances:
def singleton(array)
number = 0
array.each{|n| number = number ^ n}
number
end
irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3
^ is the bitwise XOR operator, by the way. XOR everything! HAHAHAH!
Rampion has reminded me of the inject method, so you can do this in one line:
def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end
array.inject(0) { |accum,number| accum ^ number } –
Gourmont def singleton(array): return reduce(lambda x,y:x^y, array) –
Parsimonious singleton = foldr xor 0 –
Gnosticism Assuming you can XOR the numbers, that is the key here, I believe, because of the following properties:
XOR is commutative and associative (so the order in which it's done is irrelevant).XORed with itself will always be zero.XORed with a number will be that number.So, if you simply XOR all the values together, all of the ones that occur twice will cancel each other out (giving 0) and the one remaining number (n) will XOR with that result (0) to give n.
r = 0
for i = 1 to n.size:
r = r xor n[i]
print "number is " + r
No hash table needed, this has O(n) performance and O(1) extra space (just one tiny little integer).
xor properly, or you're printing out incorrectly. You should ask a question, showing your code and specifying your language. That way, you'll get a broader response than from only me. –
Leap An answer in Ruby, assuming one singleton, and all others exactly two appearances:
def singleton(array)
number = 0
array.each{|n| number = number ^ n}
number
end
irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3
^ is the bitwise XOR operator, by the way. XOR everything! HAHAHAH!
Rampion has reminded me of the inject method, so you can do this in one line:
def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end
array.inject(0) { |accum,number| accum ^ number } –
Gourmont def singleton(array): return reduce(lambda x,y:x^y, array) –
Parsimonious singleton = foldr xor 0 –
Gnosticism "Parse the array and increment the count for number."
You could change this to "Parse the array and if the number already exists in the hash table, remove the number from the hash table". Then step 3 is just "get the only number that remains in the hash table"
XORing is just too smart to be the first thing to come to interviewee's mind –
Weinhardt Given an array of integers, every element appears twice except for one. Find that single one. We can use XOR operation. Because every number XOR itself, the results will be zero. So We XOR every integer in the array, and the result is the single one we want to find. Here is the java version code:
public class Solution {
public int singleNumber(int[] A) {
int res=0;
for(int i=0;i<A.length;i++){
res=res^A[i];
}
return res;
}
}
Follow up 1: Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? For this problem, we can't use the XOR operation.The best way to solve this problem is use "bit count". Create a 32 length int array count[32]. count[i] means how many '1' in the ith bit of all the integers. If count[i] could be divided by 3, then we ignore this bit, else we take out this bit and form the result.Below is java version code:
public class Solution {
public int singleNumber(int[] A) {
int res=0;
int[] count=new int[32];
for(int i=0;i<32;i++){
for(int j=0;j<A.length;j++){
if(((A[j]>>i)&1)==1){
count[i]=count[i]+1;
}
}
if((count[i]%3)!=0){
res=res|(1<<i);
}
}
return res;
}
}
Follow up 2: Given an array of integers, every element appears twice except for two. Find that two integers. Solution: First, XOR all the integers in the array we can get a result.(suppose it's c) Second, from the least significant bit to the most significant bit, find the first '1' position(suppose the position is p). Third, divided the integers in to two groups, the p position is '1' in one group, '0' in other group. Fourth, XOR all the integers in the two groups, and the results is the two integers we want.
I'm stealing Michael Sofaer's answer and reimplementing it in Python and C:
Python:
def singleton(array):
return reduce(lambda x,y:x^y, array)
C:
int32_t singleton(int32_t *array, size_t length)
{
int32_t result = 0;
size_t i;
for(i = 0; i < length; i++)
result ^= array[i];
return result;
}
Of course, the C version is limited to 32-bit integers (which can trivially be changed to 64-bit integers if you so desire). The Python version has no such limitation.
Here's a solution in Python that beats the Ruby one for size (and readability too, IMO):
singleton = lambda x: reduce(operator.xor, x)
Python 3.1 Solution:
>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>>
Algo 2:
This doesn't fit the bill for "no extra space" but it will cut the space unless the numbers are sorted in a certain way.
In Python:
arr = get_weird_array()
hash = {}
for number in arr:
if not number in hash:
hash[number] = 1
else:
del hash[number]
for key in hash:
print key
del hash[number]. –
Cassius © 2022 - 2024 — McMap. All rights reserved.