iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 6
0
自我挑戰組

菜鳥工程師的奇幻漂流:跟著kata活化手指和意識系列 第 6

Find the odd int

今日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網友解答

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

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


上一篇
Find the smallest integer in the array
下一篇
Sum of Digits / Digital Root
系列文
菜鳥工程師的奇幻漂流:跟著kata活化手指和意識30

尚未有邦友留言

立即登入留言