文档章节

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
二叉树的层序遍历 Binary Tree Level Order Traversal

问题: Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree , 3/ 9 20 15 7 return......

叶枫啦啦
2017/09/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux学习-1031(rsync同步工具 上)

10.28 rsync工具介绍 10.29/10.30 rsync常用选项 10.31 rsync通过ssh同步 一、 rsync工具介绍 rsync是一个同步工具,在日常的运维中常会用到。它可以本地同步,也实现可以远程两台机器同步。...

wxy丶
12分钟前
0
0
python实战一期:第一天

1. 为什么学习python 1.1 为什么要学Python? Python第一是个非常牛B的脚本语言,能满足绝大部分自动化运维的需求,又能做后端C/S架构,又能用WEB框架快速开发出高大上的Web界面,只有当你自...

laoba
14分钟前
1
0
Java并发编程学习三:线程同步的关键字以及理解

上篇文章中介绍了Java线程的带来的问题与内存模型中介绍了线程可能会引发的问题以及对应Java的内存模型,顺带介绍了Volatile和Sychronized关键字。今天对Java中涉及到的常见的关键类和关键字...

JerryLin123
21分钟前
0
0
我用代码来给你们分析一个赚钱的技巧

赚钱是个俗气的话题,但又是人人都绕不开的事情。我今天来“科学”地触碰下这个话题。 谈赚钱,就会谈到理财、投资,谈到炒股。有这样一个笑话: 问:如何成为百万富翁? 答:带一千万进入股...

crossin
21分钟前
0
0
spring MatchingBean应用

1、编写接口FactoryList import java.util.List;public interface FactoryList<E extends MatchingBean<K>, K> extends List<E> { E getBean(K factor); List<E> getBeanLi......

重城重楼
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部