文档章节

count_inversions in an integer list

ludlows
 ludlows
发布于 2014/10/07 22:54
字数 98
阅读 1
收藏 0

count = 0

def merge_sort(li):

    if len(li) < 2: return li 
    m = len(li) / 2 
    return merge(merge_sort(li[:m]), merge_sort(li[m:])) 

def merge(l, r):
    global count
    result = [] 
    i = j = 0 
    while i < len(l) and j < len(r): 
        if l[i] < r[j]: 
            result.append(l[i])
            i += 1 
        else: 
            result.append(r[j])
            count = count + (len(l) - i)
            j += 1
    result.extend(l[i:]) 
    result.extend(r[j:]) 
    return result
filename = 'Integer.txt'
unsorted = []
inFile = open(filename, 'r')
lines = inFile.readlines()
for i in lines:
    content = i.strip('\n')
    unsorted.append(int(content))



merge_sort(unsorted)
print count


© 著作权归作者所有

共有 人打赏支持
ludlows
粉丝 0
博文 15
码字总数 4195
作品 0
海淀
程序员
POJ1007·DNA Sorting

一道水题,算法也没用多么复杂的,但在G++环境下提交成功,C++会报编译不过的错误。 Description One measure of unsortedness'' in a sequence is the number of pairs of entries that are...

OldPanda
2012/06/01
0
4
POJ 1007 -- DNA Sorting

DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 94974 Accepted: 38197 Description One measure of unsortedness'' in a sequence is the number of pairs of en......

圣洁之子
2016/05/27
3
0
数组中出现频率为k次的元素 Top K Frequent Elements

问题: Given a non-empty array of integers, return the k most frequent elements. For example, Given and k = 2, return . Note: You may assume k is always valid, 1 ≤ k ≤ number......

叶枫啦啦
2017/12/26
0
0
实现迷你解析器把字符串解析成NestInteger类 Mini Parser

问题: Given a nested list of integers represented as a string, implement a parser to deserialize it. Each element is either an integer, or a list -- whose elements may also be ......

叶枫啦啦
2017/12/29
0
0
查找二叉树中出现次数最多的数 Find Mode in Binary Search Tree

问题: Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The le......

叶枫啦啦
2017/08/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
54分钟前
4
1
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
1
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
1
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
1
0
麒麟AI首席科学家现世

8月31日,华为发布了新一代顶级人工智能手机芯片麒麟980,成为全球首款7nm工艺手机芯片,AI方面也实现飞跃,支持人脸识别、物体识别、物体检测、图像分割、智能翻译等。 虽然如今人人都在热议...

问题终结者
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部