LeetCode Js-136. Single Number

    AllenLi
    LeetCode Js-Array

    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.

    給予一個非空白的整數陣列 nums，每一個元素皆出現兩次只有一個沒有。
尋找出現一次的元素。
你必須實現具有線性運行複雜度的解決方案，不能使用額外的空間。

    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

    Solution:
    1. 如果 nums 中只有一個數值，則返回該數值。
    2. 宣告一個 box 物件 {}。
    3. 將 nums 中的數值與次數依序放入 box 物件中。
    4. 依序尋找物件中數值的次數為 1，回傳該數值。

    Code 1: two for loop

    var singleNumber = function(nums) {
  if (nums.length ===1) return nums[0]

  let box = {}

  for (let i = 0; i < nums.length; i++) {
    if (box[nums[i]]) {
      box[nums[i]]++
    } else {
      box[nums[i]] = 1
    }
  }

  for (let num in box) {
    if (box[num] === 1) {
      return num;
    }
  }   
};

    FlowChart:
    Example 1

    Input: nums = [2,2,1]
nums.length = 3
box = {}

step.1
box = {'2': 1}
box = {'2': 2}
box = {'1': 1, '2': 1}

step.2 
box = {'1': 1} = 1, return i //1

    Example 2

    Input: nums = [4,1,2,1,2]
nums.lenght = 5
box = {}

step.1
box = {'4': 1}
box = {'1': 1, '4': 1}
box = {'1': 1, '2': 1, '4': 1}
box = {'1': 2, '2': 1, '4': 1}
box = {'1': 2, '2': 2, '4': 1}

step.2 
box = {'1': 2} <> 1
box = {'2': 2} <> 1
box = {'4': 1} = 1, return i //1

    Example 3

    Input: nums = [1]
nums.length = 1, return nums[0] //1

    Code 2: two for loop

    var singleNumber = function(nums) {
  if (nums.length === 1) return nums[0]

  let box = {}

  for (let i = 0; i < nums.length; i++) {
    box[nums[i]] = (box[nums[i]] || 0) + 1
  }

  for (let num in box) {
    if (box[num] === 1) return num;
  }  
};

    Code 3: XOR

    var singleNumber = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[0] ^= nums[i]
    }
    return nums[0];
};

    ^= 運算符號

    ^= : 使用二進制進行結果分配。(1 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1)
    
                                               8421
let a = 5;      // 00000000000000000000000000000101
a ^= 3;         // 00000000000000000000000000000011

console.log(a); // 00000000000000000000000000000110
// expected output: 6
Input: nums = [2,2,1]

Binary: 
       [0000]
        8421

0010 //nums[0] = 2
0010 //nums[1] = 2
-----------------
0000 // 0 

0000 //nums[0] = 0
0001 //nums[1] = 1
-----------------
0001 // 1 

0001 //nums[0] = 1

    Related Posts