小和问题

小和问题

在一个数组中，每一个元素左边比当前元素值小的元素值累加起来，叫做这个数组的小和
例如：[2,3,4,1,5]
2左边比2小的元素：无
3左边比3小的元素：2
4左边比4小的元素：2，3
1左边比1小的元素：无
5左边比5小的元素：2,3,4,1
小和small_sum = 2 + 2 + 3 + 2 + 3 + 4 + 1 = 17

解决思路

a. 将当前序列分为两个子序列，分别求其小和
b. 对a划分得到的两个子序列进行merge操作，得到合并过程产生的小和，再加上a得到的两个子序列的小和之和
c. 递归地执行a和b

merge操作采用二路归并排序的思想
求一个数组的小和，可以转化为求每个元素在小和累加过程出现的次数，然后将当前元素与出现次数相乘，累加得到小和
假设当前元素为a，a右边比a大的元素个数则为a在小和累加过程出现的次数

源代码

small_sum.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
小和问题
在一个数组中，每一个元素左边比当前元素值小的元素值累加起来，叫做这个数组的小和
例如：[2,3,4,1,5]
2左边比2小的元素：无
3左边比3小的元素：2
4左边比4小的元素：2，3
1左边比1小的元素：无
5左边比5小的元素：2,3,4,1
小和small_sum = 2 + 2 + 3 + 2 + 3 + 4 + 1 = 17
解决思路
a.将当前序列分为两个子序列，分别求其小和
b.对a划分得到的子序列进行merge操作，得到合并过程产生的小和，再加上a得到的两个子序列的小和之和
c.递归地执行a和b
"""

import random
import operator
from util import Util

def small_sum(a):
    """
    时间复杂度：O(nlogn)
    空间复杂度：O(n)
    """
    n = len(a)
    if n <= 1:
        return 0
    return __small_sum(a, 0, n-1)
    pass

def small_sum_std(a):
    """
    使用迭代的方法求解
    时间复杂度：O(n^2)
    空间复杂度：O(1)
    """
    n = len(a)
    if n <= 1:
        return 0
    res = 0
    for i in range(1, n):
        for j in range(i):
            if a[i] > a[j]:
                res += a[j]
    return res
    pass

def small_sum_test():
    for i in range(10):
        a = Util.gen_randint_list()
        k = a[:]
        b = small_sum(k)
        c = small_sum_std(a)
        print(a)
        # print(k)
        print('test: ', end = '')
        print(b)
        print(' std: ', end = '')
        print(c)
        if b == c:
            print('true')
        else:
            print('false')
    pass

def __small_sum(a, l, h):
    if l >= h:
        return 0
    mid = (l + h) // 2
    return __small_sum(a, l, mid) + __small_sum(a, mid+1, h) + __merge_other(a, l, mid, h)
    pass

def __merge(a, l, mid, h):
    res = 0

    b = a[:]
    i, j = l, mid+1
    k = l

    while i <= mid and j <= h:
        if b[i] < b[j]:
            res += b[i] * (h-j+1)
            a[k] = b[i]
            i += 1
        else:
            a[k] = b[j]
            j += 1
        k += 1

    while i <= mid:
        a[k] = b[i]
        i += 1
        k += 1
    while j <= h:
        a[k] = b[j]
        j += 1
        k += 1

    return res
    pass

def __merge_other(a, low, mid, high):
    help = []
    i, j = low, mid+1
    res = 0

    while i <= mid and j <= high:
        if a[i] < a[j]:
            res += a[i] * (high - j + 1)
            help.append(a[i])
            i += 1
        else:
            help.append(a[j])
            j += 1

    while i <= mid:
        help.append(a[i])
        i += 1
    while j <= high:
        help.append(a[j])
        j += 1

    for i in range(low, high+1):
        a[i] = help.pop(0)
    
    return res
    pass

if __name__ == '__main__':
    small_sum_test()

util.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random

class Util(object):
    """
    工具类
    """

    def gen_randint_list(n = 5, min = 0, max = 10):
        """
        生成一个随机int型列表
        """
        if n < 1 or min > max:
            return []

        rand_list = []
        for i in range(n):
            rand_list.append(random.randint(min, max))
            
        return rand_list
        pass