[讨论] 给排序过的Array 用最少运算资源找值 Kuba4ma PTT批踢踢实业坊

[讨论] 给排序过的Array 用最少运算资源找值

楼主: Kuba4ma (哦吼) 2022-05-28 12:05:53

各位大神好
本鲁最近在准备某间IC厂的面试
在网络上找到这题考古题
题目如下
```
给一个sorted array(ex: a[5]={1,1,1,0,0})，请找出第一个0的位置，请使用能降低CPU
跟memory负担的用量
```
我能想到的就只有用for loop扫过一遍而已
请问还有更好的方法吗
谢谢

作者: lingege321 (happyChicken) 2022-05-28 12:28:00

binary search

作者: lycantrope (阿宽) 2022-05-28 12:29:00

都sorted 就用binary search阿

作者: gozule (好冷啊~~) 2022-05-28 12:29:00

知道array长度，可以把内容转为整数直接查表

作者: TheOneisNEO (Thomas Anderson) 2022-05-28 22:00:00

楼上说的方法应该还是要O(n) 全部都读过而且这个array应该可以包含很多不同的值

作者: closer76 (克楼瑟) 2022-05-29 18:08:00

binary search 只要 O(log n)，而且不只 0/1 也可以做重点是 sorted

作者: Lipraxde (Lipraxde) 2022-05-29 22:37:00

量少的话可以用一些 bit operation 玩喔，LZCNT 之类的

作者: chchwy (mat) 2022-05-29 23:24:00

看到关键字sorted就知道是binary search啦

作者: hongsiangfu 2022-06-06 14:16:00

leetcode 34的需求很像

作者: wulouise (在线上!=在电脑前) 2022-06-06 22:38:00

std::uppwer_bound std::lower_bound看看很方便

继续阅读

[问题] 解题卡关password5353 [问题] atomic operation 与计算效率问题eagle32 [问题] 抽离IDE的工具链wei115 [闲聊] C++ LeetCode刷题的写法hunter73419 [问题] cannot convert int (*)[size] to int*tarantula [问题] 一个算法的问题bravooooo [问题] 有关 error: unknown type name 的问题datoguo [问题] 多线程及静态变量的问题 su27 [问题] fprintf 导致 segmentation faulteagle32 [问题] implicit conversionManOfSteel