Re: [問題] 兩個陣列元素找出不同

[Killercat (殺人貓™)]

※ 引述《jehovah (Lucius)》之銘言：
: 朋友面試遇到的問題~
: C裡面兩個陣列a b，元素都一樣，只是b比a多了一個元素
: 如何不用比較子> < ==等等 找出不同的元素
: 想了一陣子沒有頭緒～可以指點一些方向嗎^^
這題其實很簡單，不過如果標準答案supposed是這個的話
我會覺得這家公司塊陶啊....

假設這兩個陣列的element都是c(c可以是int char...etc)
首先我們先用bitwise查出他們是在第幾個bit不同
a ^ b, 然後找出第一個1就是第幾個bit不同

000000000000000000000000111111111111111111111111.....
假設sizeof(c)是1(也就是8bit) 也就是a b前三個(0 1 2)都相同
b[3]就一定是多出來的那個，ok 所以要怎麼找出來呢，很簡單
我們把a[3]全部填1 a b就會等長了，最後我們把a b做and bitwise
假設出來是d, 那d[3]就是多出來的那個數字

這不叫做技術 這叫做腦筋急轉彎.....

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.124.251.135
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1425532702.A.876.html
→ Killercat: 另外這算法其實是有一個疏漏的，看有沒有人能看出來 XD
推 Frozenmouse: 沒看錯的話 a, b 要先排序過才行吧XD
推 bibo9901: 這不是標準答案...標準答案是 fold( xor, a + b )
→ Killercat: 誒 所以a b排序都不同喔...那真的要sort一下了 XD
→ Killercat: fold...我還真的沒看過，長見識了，感謝 :D
→ azureblaze: 不需要sort 時間O(n) 空間O(1)可解
→ Killercat: 而且sort應該算是一定得用comparator了吧...
→ Killercat: 所以應該不能sort, 恩這更腦筋急轉彎了囧
推 Ebergies: fold( xor, a + b ) 這個可以詳細說明一下嗎~?
→ bibo9901: 那是 functional 的表達方法, 總之就是用 xor 把 a, b
→ bibo9901: 所有元素串起來就是答案了
推 Ebergies: 喔那我了解了, 的確是這樣
推 Frozenmouse: 長知識了…XD
→ Killercat: 這做法真的頗優秀 :D 跟x^=y^=x^=y有拼
→ Killercat: 但是....仍然是腦筋急轉彎 orz 除非以前有看過
→ azureblaze: 進階題: N個陣列 一樣有一個比其他的多了一個元素
→ azureblaze: 給了基本題的解法後進階題就不能算腦筋急轉彎了
推 Frozenmouse: N是偶數的話很明顯，奇數還在想 orz
推 bibo9901: 挑最長的一個XDD?
推 ckc1ark: 用n進位表示 在各位數rotate不進位
推 Frozenmouse: 目前想的方法都避不開if…XD