136. Single Number
Last updated
Last updated
/**
* Time complexity : O(n*1) = O(n). Time complexity of for loop is O(n).
* Time complexity of hash table(dictionary in python) operation pop is O(1).
* Space complexity : O(n). The space required by hash_table is equal to the
* number of elements in nums.
*/
class Solution {
public int singleNumber(int[] nums) {
if(nums.length == 1) return nums[0];
int value = 0;
if(nums.length%2 == 0) return value;
Map<Integer, Integer> values = new HashMap();
for(int n: nums) {
values.put(n, values.getOrDefault(n, 0)+1);
}
for(int n: nums) {
if(values.get(n) == 1) {
return n;
}
}
return value;
}
}/**
* Time complexity : O(n+n)=O(n). sum will call next to iterate through nums.
* We can see it as sum(list(i, for i in nums)) which means the time
* complexity is O(n) because of the number of elements(n) in nums.
* Space complexity : O(n+n)=O(n). set needs space for the elements in nums
*/
class Solution {
public int singleNumber(int[] nums) {
int sumOfSet = 0, sumOfNums = 0;
Set<Integer> set = new HashSet();
for (int num : nums) {
if (!set.contains(num)) {
set.add(num);
sumOfSet += num;
}
sumOfNums += num;
}
return 2 * sumOfSet - sumOfNums;
}
}/**
* Time complexity : O(n). We only iterate through nums, so the time
* complexity is the number of elements in nums.
* Space complexity : O(1)
*/
class Solution {
public int singleNumber(int[] nums) {
if(nums.length == 1) return nums[0];
int value = 0;
if(nums.length%2 == 0) return value;
for(int n: nums) {
value ^= n;
}
return value;
}
}