Home Sign Up Sign In
iOS 开发实用技术导航
NSHipster 中文版
› http://nshipster.cn/
cocos2d 开源 2D 游戏引擎
› http://www.cocos2d-iphone.org/
CocoaPods
› http://cocoapods.org/
Google Analytics for Mobile 统计解决方案
› http://code.google.com/mobile/analytics/
WWDC
› https://developer.apple.com/wwdc/
Design Guides and Resources
› https://developer.apple.com/design/
Transcripts of WWDC sessions
› http://asciiwwdc.com
Cocoa with Love
› http://cocoawithlove.com/
Cocoa Dev Central
› http://cocoadevcentral.com/
NSHipster
› http://nshipster.com/
Style Guides
› Google Objective-C Style Guide
› NYTimes Objective-C Style Guide
Useful Tools and Services
› Charles Web Debugging Proxy
› Smore
Advertisement
wezzard
V2EX  ›  iDev

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

  •   
  •   wezzard · Jun 11, 2015 · 4358 views
    This topic created in 4174 days ago, the information mentioned may be changed or developed.
    這是前幾天我遠程機試時的一道算法題，當時腦子整個是糊的，所以根本想不出來。後來昨天打了幾把風暴英雄之後又想了想——尼瑪不就是一個升級版的二分搜索嗎！？於是自己寫了一個出來，求各位算法大神拍磚。語言是 Swift 2.0。

    題目：

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

    解答：



    另外，機試時對方問到了算法複雜度，我不知道怎麼算……請問我現在這樣寫的算法複雜度還是O(log n)麼？……
  • 数组
  • 整数
  • 查找
    13 replies  •  2015-06-11 18:26:58 +08:00
    stackpop
    stackpop
    Jun 11, 2015
    1
    以前做过

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

    你看看

    Search_in_Rotated_Sorted_Array
    Search_in_Rotated_Sorted_Array_II

    两道题
    n0o0a0h0
    n0o0a0h0
    Jun 11, 2015
    2
    不懂swift啊 如果是C++ 就将数组和下标存在map或者是unordered_map(后面查找速度快很多）。很简单的。
    stackpop
    stackpop
    Jun 11, 2015
    3
    最坏是 O(N), 平均是 O(lgN)
    stackpop
    stackpop
    Jun 11, 2015
    4
    @n0o0a0h0 你这个时间复杂度是 O(1), 空间复杂度是 O(n), 一般面试会要求你写 O(lgN)的算法
    n0o0a0h0
    n0o0a0h0
    Jun 11, 2015
    5
    @stackpop 诶 最烦 算法 O(lgN) O(n) O(1), %>_<%😢
    black
    black
    Jun 11, 2015
    6
    @stackpop 他这种算法时间复杂度怎么可能O(1)...
    black
    black
    Jun 11, 2015
    7
    @stackpop 建立map的时间复杂度也要考虑，是O(n)才对
    aheadlead
    aheadlead
    Jun 11, 2015
    8
    二分断点
    liuchang0812
    liuchang0812
    Jun 11, 2015
    9
    leetcode 原题
    Golevka
    Golevka
    Jun 11, 2015
    10
    这种东西就是需要判断的case多一点而已, 写出空间O(1)时间O(logN)的应该没什么难度

    P.S. 我们在leetcode上都是20行以内A过的不明白你为什么洋洋洒洒写了这么多.
    momo1999
    momo1999
    Jun 11, 2015
    11
    一个二分真的需要写这么多吗
    GtDzx
    GtDzx
    Jun 11, 2015
    12
    楼主申请的哪家公司啊？ 还有远程机试。
    caoyue
    caoyue
    Jun 11, 2015
    13
    看来刷刷 LeetCode 还是有用的=-=
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   2019 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 14:32 · PVG 22:32 · LAX 06:32 · JFK 09:32
    ♥ Do have faith in what you're doing.