今日kata

原始題目如下:(6kyu)
Given an array of integers, find the one that appears an odd number of times.
There will always be only one integer that appears an odd number of times.

翻譯:
陣列中包含多個整數，找出唯一出現奇數次的整數為何

範例:
[20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5] 得到 5
[5,4,3,2,1,5,4,3,2,10,10] 得到 1

構想&解法

function findOdd(A) {
  let result = []
  A.sort().forEach(item => {
    if (result.length===0) {
      result.push(item);
    } else {
      if (result[0] === item) result.pop()
    }
  })
 return  result[0]
}

兩兩一組的概念，先將Array排序，不管數字大小，一樣的排在一起就好
宣告一陣列result，使用forEach check每一個元素item

• 如果result是空的，將item存入result
• 如果result已有值，檢查result中的值是否等於item
  • result[0] === item成立的話，移除result最後一個元素

最後result剩下的值，就是要找的落單整數

記得在codility也做過類似的題目，回顧當初解法如下

function solution(A) {
    output = [];
    for (let i = 0; i < A.length; i++) {
        if (output.indexOf(A[i]) == -1) {
            output.push(A[i]);
        }else if (output.indexOf(A[i]) >= 0) {
            output.splice(output.indexOf(A[i]),1);
        }
    }
    return output[0];
}

概念跟這次做codewars差別不大，宣告一空陣列output，遍歷input每一個元素，判斷要放入元素或是移除output的元素。

其他解法觀摩

const findOdd = (xs) => xs.reduce((a, b) => a ^ b);

solution中最簡潔的寫法! 使用reduce做Bitwise XOR opearator的運算!

整理用法

Bitwise XOR (^)

規則如下:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

可以簡化成:
A ^ A = 0 ( ex: 10 ^ 10 = 0 )
A ^ 0 = A

順序不影響結果(可以互換):
a ^ b ^ c = a ^ c ^ b

範例:

[10, 3, 20, 10, 3, 20, 10]
// 使用reduce進行迭代
// 第一次: 10 ^ 3 = A 
// 第二次: A ^ 20 = B 
// 第三次: B ^ 10 展開看是 10 ^ 3 ^ 20 ^ 10 
// 順序可換 變成 (10 ^ 10) ^ 3 ^ 20 = 0 ^ 3 ^ 20 = 3 ^ 20
// .....延續下去

以上範例參考自Codewars:blade-sensei網友解答

像是消泡泡遊戲一樣，找到一樣的就消掉，最後剩下的就是出現奇數次的數字。

以上為今日分享的內容，若有錯誤或是建議，請再隨時和我聯繫。