Welcome to Subscribe On Youtube

136. Single Number

Description

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Solutions

Solution 1: Bitwise Operation

The XOR operation has the following properties:

• Any number XOR 0 is still the original number, i.e., $x \oplus 0 = x$;
• Any number XOR itself is 0, i.e., $x \oplus x = 0$;

Performing XOR operation on all elements in the array will result in the number that only appears once.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

Solution 2: Using a HashSet

A direct idea is to use a HashSet due to its constant search speed. Traverse each number in the array, and if the current number is already in the HashSet, remove the number from the HashSet; otherwise, add it to the HashSet.

This is equivalent to offsetting two by two. In the end, all the numbers that appear twice are removed from the HashSet, and the only number left is the single number.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• C#
• RenderScript
• Swift

• class Solution {
      public int singleNumber(int[] nums) {
          int ans = 0;
          for (int v : nums) {
              ans ^= v;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int singleNumber(vector<int>& nums) {
          int ans = 0;
          for (int v : nums) {
              ans ^= v;
          }
          return ans;
      }
  };
  

• '''
  >>> from functools import reduce
  >>> reduce(lambda x, y: x ^ y, [3, 5, 3])
  5
  '''
  
  from functools import reduce
  
  class Solution:
      def singleNumber(self, nums: List[int]) -> int:
          return reduce(lambda x, y: x ^ y, nums)
  
  ############
  
  class Solution(object):
    def singleNumber(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      for i in range(1, len(nums)):
        nums[0] ^= nums[i]
      return nums[0]
  

• func singleNumber(nums []int) (ans int) {
  	for _, v := range nums {
  		ans ^= v
  	}
  	return
  }
  

• function singleNumber(nums: number[]): number {
      return nums.reduce((r, v) => r ^ v);
  }
  
  

• /**
   * @param {number[]} nums
   * @return {number}
   */
  var singleNumber = function (nums) {
      return nums.reduce((a, b) => a ^ b);
  };
  
  

• public class Solution {
      public int SingleNumber(int[] nums) {
          return nums.Aggregate(0, (a, b) => a ^ b);
      }
  }
  

• impl Solution {
      pub fn single_number(nums: Vec<i32>) -> i32 {
          nums.into_iter()
              .reduce(|r, v| r ^ v)
              .unwrap()
      }
  }
  
  

• class Solution {
      func singleNumber(_ nums: [Int]) -> Int {
          return nums.reduce(0, ^)
      }
  }
  

All Problems

All Solutions