PTT數位生活區 / C_and_CPP (C/C++)

[討論] 給排序過的Array 用最少運算資源找值

看板C_and_CPP (C/C++)作者時間2年前 (2022/05/28 12:05), 2年前編輯推噓4(4推 0噓 7→)
留言11則, 9人參與, 最新討論串1/2 (看更多)
各位大神好 本魯最近在準備某間IC廠的面試 在網路上找到這題考古題 題目如下 ``` 給一個sorted array(ex: a[5]={1,1,1,0,0})，請找出第一個0的位置，請使用能降低CPU 跟memory負擔的用量 ``` 我能想到的就只有用for loop掃過一遍而已 請問還有更好的方法嗎 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.82.35 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1653710755.A.F73.html
→
05/28 12:28, 2年前 , 1F
binary search
05/28 12:28, 1F
→
05/28 12:29, 2年前 , 2F
都sorted 就用binary search阿
05/28 12:29, 2F
對耶 居然沒想到XD 一直往Bit operation的方向想
推
05/28 12:29, 2年前 , 3F
知道array長度，可以把內容轉為整數直接查表
05/28 12:29, 3F
了解 感謝你 ※ 編輯: Kuba4ma (111.241.82.35 臺灣), 05/28/2022 13:00:23
→
05/28 22:00, 2年前 , 4F
樓上說的方法應該還是要O(n) 全部都讀過
05/28 22:00, 4F
→
05/28 22:01, 2年前 , 5F
而且這個array應該可以包含很多不同的值
05/28 22:01, 5F
推
05/29 18:08, 2年前 , 6F
binary search 只要 O(log n)，而且不只 0/1 也可以做
05/29 18:08, 6F
→
05/29 18:08, 2年前 , 7F
重點是 sorted
05/29 18:08, 7F
→
05/29 22:37, 2年前 , 8F
量少的話可以用一些 bit operation 玩喔，LZCNT 之類的
05/29 22:37, 8F
→
05/29 23:24, 2年前 , 9F
看到關鍵字sorted就知道是binary search啦
05/29 23:24, 9F
推
06/06 14:16, , 10F
leetcode 34的需求很像
06/06 14:16, 10F
推
06/06 22:38, , 11F
std::uppwer_bound std::lower_bound看看 很方便
06/06 22:38, 11F
‣ 更多 Kuba4ma 的文章
文章代碼(AID): #1YaP-Zzp (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Kuba4ma 的文章
文章代碼(AID): #1YaP-Zzp (C_and_CPP)