V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sunhk25
V2EX  ›  配件

求解 Python 面试题:

  •  
  •   sunhk25 · 2017-07-11 13:33:42 +08:00 · 5665 次点击
    这是一个创建于 2452 天前的主题,其中的信息可能已经有所发展或是发生改变。

    求解 python 面试题:

    def solution(A):
        N = len(A)
        result = 0
        for i in xrange(N):
            for j in xrange(N):
                if A[i] == A[j]:
                    result = max(result, abs(i - j))
        return result
    

    当数组极大时,效率不好,求如何改??!!

    41 条回复    2019-01-24 14:44:41 +08:00
    holajamc
        1
    holajamc  
       2017-07-11 13:49:53 +08:00   ❤️ 1
    这……不永远都是 0 么…
    capbone
        2
    capbone  
       2017-07-11 13:51:36 +08:00   ❤️ 1
    计算相距最远的两个相等元素?
    先用 argsort 返回排序序号,再分组求最大值,应该会高效不少吧?
    sunhk25
        3
    sunhk25  
    OP
       2017-07-11 13:52:33 +08:00
    @capbone 是的,有參考代碼么
    sunhk25
        4
    sunhk25  
    OP
       2017-07-11 13:53:26 +08:00
    @holajamc 0 並不重要,给的数组有一样的值就可以了,关键是算法
    capbone
        5
    capbone  
       2017-07-11 13:53:45 +08:00
    没... 我也只是随便一想给了个大概思路...
    braineo
        6
    braineo  
       2017-07-11 13:56:41 +08:00
    @capbone 记录出现过的 index 呢?不是 1 pass 么
    shuson
        7
    shuson  
       2017-07-11 13:59:42 +08:00
    ```
    def sol(A):
    n = len(A)
    for i in range(n):
    j = n-1
    while j > i:
    if A[i] == A[j]:
    return j - i
    j -= 1
    return 0
    ```
    geelaw
        8
    geelaw  
       2017-07-11 14:03:39 +08:00   ❤️ 2
    用字典和合适的 hash 函数族可以做附加空间 O(n),期望时间 O(n) 的。
    用排序可以做附加空间 O(n),时间 O(nlogn) 的。
    ZRS
        9
    ZRS  
       2017-07-11 14:04:24 +08:00
    @shuson 这么改复杂度还是 N^2 这个级别的啊...
    holyghost
        10
    holyghost  
       2017-07-11 14:06:16 +08:00   ❤️ 1
    hashmap 记录第一次出现该元素的 index
    后面就是更新 max = (currentIndex - index) 了
    空间 O(n) 时间 O(n)
    shuson
        11
    shuson  
       2017-07-11 14:07:01 +08:00
    tkpc
        12
    tkpc  
       2017-07-11 14:08:51 +08:00
    V = {}
    for i,x in enumerate(A):
    if x in V: V[x][1] = i
    else: V[x] = [i,i]
    print max( (b-a) for a,b in V.itervalues() )
    Valyrian
        13
    Valyrian  
       2017-07-11 14:14:15 +08:00
    难道不是直接 return max(A) - min(A)
    csdreamdong
        14
    csdreamdong  
       2017-07-11 14:14:47 +08:00
    0 0 我果然还是菜。。真心求问。这题想描述什么问题。
    Valyrian
        15
    Valyrian  
       2017-07-11 14:14:51 +08:00
    @Valyrian 看错题了。。
    yunkchen
        16
    yunkchen  
       2017-07-11 14:18:55 +08:00
    import collections

    def solution(A):
    l_count = collections.Counter(A)
    repeats = [k for k, v in l_count.items() if v > 1]
    ix_dict = collections.defaultdict(lambda: set())
    for i in range(len(A)):
    if A[i] in repeats:
    ix_dict[A[i]].add(i)
    return max([max(ix_value)-min(ix_value) for ix_value in ix_dict.values()])
    chroming
        17
    chroming  
       2017-07-11 14:29:34 +08:00
    一个小优化

    '''

    def solution(A):
    N = len(A)
    result = 0
    for i in xrange(N):
    for j in xrange(i, N):
    if A[i] == A[j]:
    result = max(result, abs(i - j))
    return result

    '''
    chroming
        18
    chroming  
       2017-07-11 14:30:27 +08:00
    回复怎么不支持 markdown 了

    把 for j in xrange(N)改成 for j in xrange(i, N):
    gimp
        19
    gimp  
       2017-07-11 14:35:11 +08:00


    谁帮我看着这个时间复杂度多少,谢谢
    ty89
        20
    ty89  
       2017-07-11 14:35:34 +08:00
    ```

    def foo(a):
    m = {}
    max_delta = 0
    for current_index in xrange(len(a)):
    s = a[current_index]
    if not m.has_key(s):
    m[s] = {'first_index':current_index}
    delta = 0
    else:
    delta = abs(m[s]['first_index'] - current_index)

    max_delta = max(max_delta, delta)
    return max_delta

    ```
    ty89
        21
    ty89  
       2017-07-11 14:38:00 +08:00
    悲剧,评论吞代码

    ![]( )
    takeoffyoung
        22
    takeoffyoung  
       2017-07-11 15:03:41 +08:00
    takeoffyoung
        23
    takeoffyoung  
       2017-07-11 15:04:42 +08:00
    [Imgur]( )
    di94sh
        24
    di94sh  
       2017-07-11 15:15:32 +08:00
    这样时间复杂度是不是 O(N)
    [Imgur]( http://imgur.com/a/zTNYd)
    di94sh
        25
    di94sh  
       2017-07-11 15:16:08 +08:00
    Yvette
        26
    Yvette  
       2017-07-11 15:45:32 +08:00
    没看错的话作用是求数组中相同值的最远距离吗,可以先 enumerator 之后根据 key 排序再找相同字段的最大长度,算法刚开始学不太懂怎么算时间复杂度……懂得麻烦帮忙看下

    zlin3000
        27
    zlin3000  
       2017-07-11 16:27:49 +08:00 via Android
    因为是求最远相同元素距离,感觉可以从最远距离直接下手,即最大的可能最远距离只有一种,即第一个元素和最后一个元素,下一层可能得到最远距离的是两种即第一个和倒数第二个,第二个和倒数第一个,然后以此类推。
    backto17
        28
    backto17  
       2017-07-11 16:29:34 +08:00
    @gimp o(n), 另外可以用 defaultdict, 可以少了自己去判断存不存在
    aaronzjw
        29
    aaronzjw  
       2017-07-11 16:31:49 +08:00 via Android
    考虑下哪些元素重复,然后对重复的元素进行计算
    zlin3000
        30
    zlin3000  
       2017-07-11 16:40:51 +08:00 via Android
    这么一说,如果不考虑空间成本的情况下,时间应该是 O(n),遍历数组,用字典记住每个元素出现的最初位置,然后一个 max value 记入当前最远距离。
    QAPTEAWH
        32
    QAPTEAWH  
       2017-07-11 17:56:04 +08:00   ❤️ 1
    动态规划
    D(i,j) =
    j - i, if item[i] = item[j], or
    max{D(i+1, j), D(i, j-1)}
    cxyfreedom
        33
    cxyfreedom  
       2017-07-11 18:27:48 +08:00
    ```
    max([(len(l) - l[::-1].index(i) - 1) - l.index(i) for i in set(l)])
    ```
    sky101001
        34
    sky101001  
       2017-07-11 19:11:11 +08:00 via iPad
    第一反应是排序复杂度是 O(nlogn),再比较相邻元素,复杂度是 O(n),选出最大间隔 O(nlogn)。最终时间复杂度可以是 O(nlogn)。
    不过总觉得有更快的方法,容我想想
    xiaket
        35
    xiaket  
       2017-07-12 06:49:25 +08:00
    @Livid 从回复看,绝大多数人都希望回复支持 markdown, 至少求添加对代码块的支持....
    ArcticL
        36
    ArcticL  
       2017-07-12 14:24:43 +08:00
    @zlin3000 有一点是当 result 越小,甚至等于 0 时,时间成本比原方案更大
    def solution(A):
    arrayLength = len(A)
    for result in range(arrayLength, -1, -1):
    for i in range(arrayLength):
    if i + result < arrayLength and A[i] == A[i + result]:
    return result
    zlin3000
        37
    zlin3000  
       2017-07-12 18:07:18 +08:00
    @ArcticL
    原方案时间复杂度 是 固定的 O ( n^2 )
    我的第一个方案,最差 case 是 O ( n^2 ),1 + 2 + 3 + 4 + 5 + ... + n-1 = (n*(n-1))/2
    所以 时间成本并不会比原方案更大。
    ArcticL
        38
    ArcticL  
       2017-07-12 20:19:48 +08:00
    @zlin3000 有代码么?这些概念的东西不好理解。。。
    zlin3000
        39
    zlin3000  
       2017-07-13 01:58:51 +08:00
    @ArcticL 代码:
    ```python

    def solution(A):
    # 两个元素之间的可能最长距离为数组长度-1
    max_dist = len(A) - 1

    # 从最长距离开始逐渐往下递减
    for dist in range(max_dist, 0, -1):
    # 因为是按距离长度查找, 固每次只要查看可能可以达成当前长度距离的数组
    # 所以第一次只能是 第一个元素和最后一个元素;
    # 第二次是第一个和倒数第二个, 第二个和最后一个元素; 第三次可以此类推
    # 因此是 1 + 2+ 3 + ... + n-1
    for i in range(len(A) - dist):
    if A[i] == A[i+dist]:
    return dist

    # 如果循化结束没有答案,则表示没有匹配数组
    return 0

    ```
    ArcticL
        40
    ArcticL  
       2017-07-13 09:41:12 +08:00
    @zlin3000 哦,我懂了,当 result=0 时,虽然我判断了,但第二层循环等于又完全遍历了,是这个意思吧。
    719465553
        41
    719465553  
       2019-01-24 14:44:41 +08:00
    新建一个数组放下标,快排之后一个 for 算下标差就好了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3263 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 14:07 · PVG 22:07 · LAX 07:07 · JFK 10:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.