• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode -260- The number III that appears only once

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once. You can return the answers in any order.

 

Advanced: Your algorithm should have linear time complexity. Can you do this using just constant space complexity?

 

Example 1:

Input: nums = [1,2,1,3,2,5] output: [3,5] explanation: [5, 3] are also valid answers.Copy the code

Example 2:

Input: nums = [-1,0] Output: [-1,0]Copy the code

Example 3:

Input: nums = [0,1] output: [1,0]Copy the code

Tip:

  • 2 <= nums.length <= 3 *
    1 0 4 10^4
  • –
    2 3 1 2^31     <= nums[i] <=
    2 3 1 2^31     – 1
  • All numbers in NUMS occur twice except for two integers that occur only once

Idea 1: XOR

  • Find sum by xor of all numbers
  • Sum is the xor sum of two different numbers
  • Two different numbers will have different k bits
  • So that satisfies our condition, and we just put two of them in the array
class Solution {
        public int[] singleNumber(int[] nums) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum ^= nums[i];
            }
            int k = -1;
            for (int i = 31; i >= 0 && k == -1; i++) {
                if (((sum >> i) & 1) = =1) { k = i; }}int[] ans = new int[2];
            for (int i : nums) {
                if (((i >> k) & 1) = =1) {
                    ans[1] ^= i;
                }
                else {
                    ans[0] ^= i; }}returnans; }}Copy the code
  • Time complexity (O(n))
  • Space complexity (O(1))