Pulpcode

捕获，搅碎，拼接，吞咽

0%

从两个已排序数组中寻找第k个元素

发表于 更新于 分类于 Valine：

前言

其实，我最不爱做笔试题了，实际上在这几年的面试经验来看，大部分求职者其实也不喜欢做笔试题，有的同事甚至跟我说，一让他做笔试题就想走了。而且一些公司也不安排什么笔试题，可能校招会有笔试题，社会招聘，都是现场给纸和笔，一边问一边写的。而且我也真不明白这些笔试题是否能选拔出来那些高智商的，可培养的员工？他们算法好的要命。反正我不这样认为，面试这东西，可能真的需要有经验的人，多聊，多沟通，到底做过什么样的项目，是否对技术本身有理解。

以上就当我扯淡了，我可能最近会写几篇解答笔试题的博客。

当然这个答案完全是我自己写的，如果有什么不对的地方，或者有更好的解法，还请指正。

题目

已知两个长度为N的数组A，B，已分别按升序排列
A. 求第N和N+1个数，伪代码实现，并估算复杂度。
B. 如果你的揭发时间复杂度为O(logN)，请考虑复杂度更低的算法。

解答(思路1)

首先我为数组A，和数组B分别设计一个游标，然后通过类似“归并排序的方式”，
遍历这两个数组，当大计数器（0~2N-1）到N的时候，就可以了，输出break。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import random

def gen_random_sort_list():
    """
    返回一个有序的随机数组(0, 99),长度为20
    """
    l = [random.randint(0, 99) for i in range(20)]
    l.sort()
    return l

def merge_list(l1, l2):
    """
    此函数验证结果是否正确
    """
    l3 = l1 + l2
    l3.sort()
    return l3

def main():
    l1 = gen_random_sort_list()
    l2 = gen_random_sort_list()
    print l1
    print l2
    # j为l1的当前元素下标
    j = 0
    # k为l2的当前元素下标
    k = 0
    # t用来存放第i个元素的值
    t = None
    # N
    n = 19
    # N + 1
    nadd1 = 20
    l3 = merge_list(l1, l2)
    print "N应为:{},N+1应为:{}".format(l3[n], l3[nadd1])

    for i in range(40):
        # 第n的元素在第n次才被放好，所以n+1才能打印
        if j <= n and k <= n:
            if l1[j] <= l2[k]:
                t = l1[j]
                j = j+1
            else:
                t = l2[k]
                k = k+1
        elif j <= n and k > n:
            t = l1[j]
            j = j + 1
        elif k <= n and j > n:
            t = l2[k]
            k = k + 1

        if i == n :
            print "N:{}".format(t)
        elif i == nadd1:
            print "N+1:{}".format(t)
            break


if __name__ == "__main__":
    main()

我理解时间复杂度应该为：O(n)

思路2

当然比这个稍微搓一点的做法就是先直接使用归并排序，然后再直接取出第N，第N+1个数，那么可以知道这个做法的时间复杂度是o(2n),当然这里面还有一些空间复杂度。

思路3

我们可以使用类似折半查找的枝剪，并假设如果合并，但其实并不真的合并。

首先对l1，l2两个数组进行对半切。比如l1数组，从v1开始切，那么v1就是l1的第v1个元素，它的下标为v1-1,它的前面就有v1-1个元素。同理我们能够找出l2的v2。

那么当l1[v1-1]>=l2[v2-1]时候，可以确定,如果进行归并，那么l1前面至少有v1-1+v2-1+1个元素,那么如果这个值比k还要大，那么k肯定不会落到l1[v1-1]后面的元素中，包括其自己，那么就可以进行枝剪。

但是如果v1-1+v2-1+1个元素，比k的值要小，那么k肯定不会落到l2[v2-1]的前面的元素，包括其自己，那么也可以进行枝剪，但是这种枝剪需要注意的是，因为枝剪的是前方的元素，所以递归后的自问题，变成了“找第k-v2个元素”。

同理可以分别讨论l1[v1-1]<l2[v2-1]的两种情况。

何时停止

递归问题的一个头疼问题就是，这个子问题什么时候停止，实际上，只要我们枝剪到一方再没有元素了，那么就变成了另一个数组求第k个元素的问题了，走索引就出来。

注意事项

在写代码的时候一定不能被开闭区间，下标从0开始之类的问题搞混了，多一少一的问题，常常使你的程序难以调试。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def get_k(k, l1=None, l2=None):
    """
    在l1,l2中寻找第k个元素
    其中l1,l2都为有序数组
    """
    m = len(l1)
    n = len(l2)

    # 第k个元素的下标为k-1
    if m == 0:
        return l2[k-1]
    elif n == 0:
        return l1[k-1]

    if m % 2 == 0:
        v1 = m / 2
    else:
        v1 = m / 2 + 1
    if n % 2 == 0:
        v2 = n / 2
    else:
        v2 = n / 2 + 1

    # v1 为l1的第v1个元素，它的下标为v1-1,它的前面有v1-1个元素
    # v2 为l2的第v2个元素，它的下标为v2-1,它的前面有v2-1个元素

    if v1-1+v2-1+1 >= k :
        if l1[v1-1] >= l2[v2-1]:
            # l1[v1-1:m]的元素肯定是多余的(包括v1)，因为k根本坐落不到
            return bar(k, l1[:v1-1], l2[::])
        else:
            # l2[v2-1:n]的元素肯定是多余的(包括v2)，因为k根本坐落不到
            return bar(k, l1[::], l2[:v2-1])
    else:
        if l1[v1-1] >= l2[v2-1]:
            # l2[0:v2]的元素肯定是多余的(包括v2)， 因为k肯定不再其中
            return bar(k-v2, l1[::], l2[v2:])
        else:
            # l1[0:v1]的元素肯定是多余的(包括v1)，因为k肯定不再其中
            return bar(k-v1, l1[v1:], l2[::])
def main3():
    l1 = gen_random_sort_list()
    l2 = gen_random_sort_list()
    print l1
    print l2
    print get_k(10, l1, l2)
    l3 = merge_list(l1, l2)
    print "l3:{}".format(l3)
    print "l3应当为:{}".format(l3[10-1])

复杂度

如果l1的长度为m,l2的长度为n,那么这个解法的时间复杂度是O(lgm+lgn)