一到算法題的解答，求拍磚

[wezzard]

這是前幾天我遠程機試時的一道算法題，當時腦子整個是糊的，所以根本想不出來。後來昨天打了幾把風暴英雄之後又想了想——尼瑪不就是一個升級版的二分搜索嗎！？於是自己寫了一個出來，求各位算法大神拍磚。語言是 Swift 2.0。

題目：

在循环有序整数数组中查找指定元素，也就是说在类似这样的{12,16,18,20,41,100,1,4,6,9}整数数组中查找指定的元素
(找出一个返回下标即可)

解答：

https://gist.github.com/WeZZard/87a6c3f234f97533b5c2

另外，機試時對方問到了算法複雜度，我不知道怎麼算……請問我現在這樣寫的算法複雜度還是O(log n)麼？……

[stackpop]

以前做过

https://github.com/sjtubinlong/Programming-Challenges/tree/master/leetcode

你看看

Search_in_Rotated_Sorted_Array
Search_in_Rotated_Sorted_Array_II

两道题

[n0o0a0h0]

不懂swift啊 如果是C++ 就将数组和下标存在map或者是unordered_map(后面查找速度快很多）。很简单的。

[stackpop]

最坏是 O(N), 平均是 O(lgN)

[stackpop]

@n0o0a0h0 你这个时间复杂度是 O(1), 空间复杂度是 O(n), 一般面试会要求你写 O(lgN)的算法

[n0o0a0h0]

@stackpop 诶 最烦 算法 O(lgN) O(n) O(1), %>_<%😢

[black]

@stackpop 他这种算法时间复杂度怎么可能O(1)...

[black]

@stackpop 建立map的时间复杂度也要考虑，是O(n)才对

[aheadlead]

二分断点

[liuchang0812]

leetcode 原题

[Golevka]

这种东西就是需要判断的case多一点而已, 写出空间O(1)时间O(logN)的应该没什么难度

P.S. 我们在leetcode上都是20行以内A过的不明白你为什么洋洋洒洒写了这么多.

[shuax]

一个二分真的需要写这么多吗

[GtDzx]

楼主申请的哪家公司啊？ 还有远程机试。

[caoyue]

看来刷刷 LeetCode 还是有用的=-=