文档章节

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
海淀
程序员
私信 提问
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
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
数组中出现频率为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

没有更多内容

加载失败,请刷新页面

加载更多

rabbitMQ 在spring 的使用

一、准备工作 maven依赖 <dependency>  <groupId>com.rabbitmq</groupId>  <artifactId>amqp-client</artifactId>  <version>4.0.2</version></dependency> <dependency......

狼王黄师傅
昨天
1
0
Android JNI总结

0x01 JNI介绍 JNI是Java Native Interface的缩写,JNI不是Android专有的东西,它是从Java继承而来,但是在Android中,JNI的作用和重要性大大增强。 JNI在Android中起着连接Java和C/C++层的作...

天王盖地虎626
昨天
1
0
大数据教程(11.8)Hive1.2.2简介&初体验

上一篇文章分析了Hive1.2.2的安装,本节博主将分享Hive的体验&Hive服务端和客户端的使用方法。 一、Hive与hadoop直接的关系 Hive利用HDFS存储数据,利用MapReduce查询数据。 二、Hive与传统数...

em_aaron
昨天
3
0
跟我学Spring Cloud(Finchley版)-15-Hystrix监控详解

Hystrix提供了监控Hystrix Command的能力,本节来详细探讨。 监控端点与数据 应用整合Hystrix,同时应用包含spring-boot-starter-actuator 依赖,就会存在一个/actuator/hystrix.stream 端点...

周立_ITMuch
昨天
6
0
day26:shell题

1、 判断当前主机的CPU生产商,其信息在/proc/cpuinfo文件中vendor id一行中。 如果其生产商为AuthenticAMD,就显示其为AMD公司; 如果其生产商为GenuineIntel,就显示其为Intel公司; 否则,...

芬野de博客
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部