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 · 3996 views
    This topic created in 4013 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
        1
    stackpop  
       Jun 11, 2015
    以前做过

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

    你看看

    Search_in_Rotated_Sorted_Array
    Search_in_Rotated_Sorted_Array_II

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

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