Python之小和问题_小和问题 python

**

Python之小和问题

**
小和问题就是在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和

例子：[1, 3, 4, 2, 5]
左边比1小的数： None
左边比3小的数：1
左边比4小的数：1,3
左边比2小的数：1
左边比5小的数：1,3,4,2
所以小和为：1+1+3+1+1+3+4+2=16

**普通解法**
arr = [1, 3, 4, 2, 5]
def SmallSum(arr):
    n = len(arr) 
    SmallSum = 0
    for i in range(n):     
        for j in range(i):
            if arr[j]<arr[i]:
                SmallSum += arr[j]
    return SmallSum

print(SmallSum(arr))
1
2
3
4
5
6
7
8
9
10
11
12

**归并排序解法**
#!/usr/bin/python
# -*- coding: utf-8 -*-
def small_sum(arr):
    if not arr or len(arr)<1:
        return 0
    return merge_sort(arr, 0, len(arr) - 1)

def merge_sort(arr, l, r):
    if l == r :
        return 0
    mid = l + ((r - l) >> 1)
    return merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r) + merge(arr, l, mid, r)

def merge(arr, l, m, r):
    help = []
    p1 = l
    p2 = m + 1
    res = 0
    while p1 <= m and p2 <= r :
        res += (r - p2 + 1) * arr[p1] if arr[p1] < arr[p2] else  0
        if arr[p1] < arr[p2] :
            help.append(arr[p1])
            p1 += 1
        else :
            help.append(arr[p2])
            p2 += 1

    while p1 <= m :
        help.append(arr[p1])
        p1 += 1
    while p2 <= r :
        help.append(arr[p2])
        p2 += 1
    for i in range(len(help)):
        arr[l + i] = help[i]
    return res;

from array import array

arr = array('b', (1, 2, 3))
print(small_sum(arr))

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