Sort a Special Array

Posted on | Visitors: 

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
# Cloudin云英 面试题
def sort_special_array(a):
    if not a:
        return a

    ls = []
    i = 0
    j = len(a) - 1
    k = 0
    if a[0] < a[-1]:
        ls.append(a[0])
        i += 1
    else:
        ls.append(a[-1])
        j -= 1

    while i <= j:
        if ls[k] == a[i]:
            i += 1
            continue
        if ls[k] == a[j]:
            j -= 1
            continue
        if a[i] < a[j]:
            ls.append(a[i])
            i += 1
            k += 1
        else:
            ls.append(a[j])
            j -= 1
            k += 1

    return ls


if __name__ == "__main__":
    a = [-4, -2, -2, 0, 4, 5, 7, 8, 7, 5, 4, 3, 2, 0, 0, -3, -5]
    assert sort_special_array(a) == [-5, -4, -3, -2, 0, 2, 3, 4, 5, 7, 8]
    a = [-4, -2, -2, 0, 4, 5, 7]
    assert sort_special_array(a) == [-4, -2, 0, 4, 5, 7]
    a = [4, 2, 2]
    assert sort_special_array(a) == [2, 4]
    a = [5]
    assert sort_special_array(a) == [5]
    a = []
    assert sort_special_array(a) == []