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

作者: Killercat (殺人貓™)   2015-03-05 13:18:20
※ 引述《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]就是多出來的那個數字
這不叫做技術 這叫做腦筋急轉彎.....
作者: Killercat (殺人貓™)   2015-03-05 13:19:00
另外這算法其實是有一個疏漏的,看有沒有人能看出來 XD
作者: Frozenmouse (*冰之鼠*)   2015-03-05 13:38:00
沒看錯的話 a, b 要先排序過才行吧XD
作者: bibo9901 (function(){})()   2015-03-05 13:49:00
這不是標準答案...標準答案是 fold( xor, a + b )
作者: Killercat (殺人貓™)   2015-03-05 13:50:00
誒 所以a b排序都不同喔...那真的要sort一下了 XDfold...我還真的沒看過,長見識了,感謝 :D
作者: azureblaze (AzureBlaze)   2015-03-05 13:59:00
不需要sort 時間O(n) 空間O(1)可解
作者: Killercat (殺人貓™)   2015-03-05 14:00:00
而且sort應該算是一定得用comparator了吧...所以應該不能sort, 恩這更腦筋急轉彎了囧
作者: Ebergies (火神)   2015-03-05 14:01:00
fold( xor, a + b ) 這個可以詳細說明一下嗎~?
作者: bibo9901 (function(){})()   2015-03-05 14:04:00
那是 functional 的表達方法, 總之就是用 xor 把 a, b所有元素串起來就是答案了
作者: Ebergies (火神)   2015-03-05 14:05:00
喔那我了解了, 的確是這樣
作者: Frozenmouse (*冰之鼠*)   2015-03-05 14:06:00
長知識了…XD
作者: Killercat (殺人貓™)   2015-03-05 14:06:00
這做法真的頗優秀 :D 跟x^=y^=x^=y有拼但是....仍然是腦筋急轉彎 orz 除非以前有看過
作者: azureblaze (AzureBlaze)   2015-03-05 14:32:00
進階題: N個陣列 一樣有一個比其他的多了一個元素給了基本題的解法後進階題就不能算腦筋急轉彎了
作者: Frozenmouse (*冰之鼠*)   2015-03-05 15:02:00
N是偶數的話很明顯,奇數還在想 orz
作者: bibo9901 (function(){})()   2015-03-05 19:49:00
挑最長的一個XDD?
作者: ckc1ark (偽物)   2015-03-05 21:48:00
用n進位表示 在各位數rotate不進位
作者: Frozenmouse (*冰之鼠*)   2015-03-06 01:04:00
目前想的方法都避不開if…XD

Links booklink

Contact Us: admin [ a t ] ucptt.com