[問題] 面試題-關於排序後的陣列取值

看板C_and_CPP作者 ( U U)時間11年前 (2012/12/30 11:42), 編輯推噓12(12推 0噓 19→)
留言31則, 12人參與, 最新討論串1/1
問題(Question)： 面試的時候有一家只考一題，似乎很重視這個觀念，題目如下 「有一個按照大小排序好的陣列 例如 [1,1,1,5,5,5,5,5,6,6] 如何在不使用API或library的情況下 求得數字5有幾個？」 我只會用最普通的方法，也就是用迴圈掃一遍，然後累計有幾個5出現 有人有其他漂亮的解法嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.165.224.145 ※ 編輯: milonga332 來自: 118.165.224.145 (12/30 11:45)
推
12/30 11:47, , 1F
自己實作upper_bound()和lower_bound()然後相減 （？
12/30 11:47, 1F
→
12/30 11:48, , 2F
不知道是要哪方面漂亮？不過這樣複雜度降到O(logN)
12/30 11:48, 2F
推
12/30 11:50, , 3F
先用binary search找到target, 然後左右各看看有幾個?
12/30 11:50, 3F
對呀..我應該要問一下面試官，他們的訴求到底是什麼才對 不過既然不能使用API或library的話，應該是不能使用任何function吧 我本來想說是不是要操弄索引，或者是指標有沒有奇淫異技可用... ※ 編輯: milonga332 來自: 118.165.224.145 (12/30 12:40)
→
12/30 13:29, , 4F
要你手爆二分搜XD?
12/30 13:29, 4F
→
12/30 14:19, , 5F
這家面試前該不會有要你簽NDA..
12/30 14:19, 5F
→
12/30 14:45, , 6F
要個判斷式跳出的動作
12/30 14:45, 6F
→
12/30 14:54, , 7F
當然...很多無腦的面試官都在事後才說:假設這個陣列很大...
12/30 14:54, 7F
推
12/30 15:43, , 8F
其實這面試官自己不會 拿出來問答案(咦?
12/30 15:43, 8F
→
12/30 19:25, , 9F
更，以前我公司水星SA就是這樣，樓上是不是跟我同事過XD
12/30 19:25, 9F
推
12/30 21:54, , 10F
「排序好的陣列」,很多面試都會假設這前提看思考力。
12/30 21:54, 10F
→
12/30 22:17, , 11F
其實呢, 又沒有說 這個 target 出現佔所有數目的比例
12/30 22:17, 11F
→
12/30 22:18, , 12F
是多少, 所以所謂漂亮的解法就是符合你需求的解法, 這
12/30 22:18, 12F
→
12/30 22:18, , 13F
麼小的陣列當然一個迴圈搞定才是最佳解
12/30 22:18, 13F
推
12/30 23:13, , 14F
不過話說回來 這世界上哪有 已經排序好才來統計
12/30 23:13, 14F
→
12/30 23:14, , 15F
其中有多少相同 case 的需求 ?
12/30 23:14, 15F
推
12/30 23:24, , 16F
難講吧！排序過的array接下來要做任何事都方便多,不是嗎?
12/30 23:24, 16F
→
12/30 23:25, , 17F
(像是搜尋用到特多的時候,先做排序不是比較好嗎?)
12/30 23:25, 17F
推
12/30 23:43, , 18F
我的意思是 統計要在排序 or 在塞資料的時候就偷偷作啊
12/30 23:43, 18F
→
12/30 23:44, , 19F
如果 是真正要要求效率的話 把cost點放在排序後計算
12/30 23:44, 19F
→
12/30 23:44, , 20F
實在是有點詭異 orz
12/30 23:44, 20F
推
12/30 23:47, , 21F
呵,您說的也是,只是前提可能會是,sort要自己寫,且寫得不慢
12/30 23:47, 21F
→
12/31 00:04, , 22F
條件給太少的情況根本不可有什麼漂亮的解法, 即使只是
12/31 00:04, 22F
→
12/31 00:04, , 23F
隨便想出來的題目
12/31 00:04, 23F
推
12/31 02:04, , 24F
排序後統計是有原因的，因為排的時候還不知道要統計啥
12/31 02:04, 24F
→
12/31 02:05, , 25F
比如說資料庫以前就建好了，後來才想增加某種查詢方式
12/31 02:05, 25F
→
12/31 02:05, , 26F
倒不如說這才符合真實世界的情況 也就是需求一直在變
12/31 02:05, 26F
大家考慮的點真多(筆記筆記..) 現在想想，應該藉著詢問對方訴求的同時，展現自己懂的範圍才對 ※ 編輯: milonga332 來自: 118.165.224.145 (12/31 10:58)
→
12/31 12:50, , 27F
想用你就沒什麼意見 不想用你怎麼解都可以吐
12/31 12:50, 27F
推
12/31 13:43, , 28F
Q_Q 我到沒想過資料庫欸 if 這問題存在 該不會是要測試
12/31 13:43, 28F
→
12/31 13:44, , 29F
有沒有 1/2 逼近法這種概念吧 orz
12/31 13:44, 29F
推
12/31 21:06, , 30F
關鍵就在二分搜尋法可以 impl. 的方法太多了 !!
12/31 21:06, 30F
推
12/31 21:40, , 31F
二分前後搜?
12/31 21:40, 31F
‣ 更多 milonga332 的文章
文章代碼(AID): #1GtxW_Mp (C_and_CPP)