Tasks Details
medium
Compute number of inversion in an array.
Task Score
100%
Correctness
100%
Performance
100%
An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
Write a function:
def solution(A)
that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.
For example, in the following array:
A[0] = -1 A[1] = 6 A[2] = 3 A[3] = 4 A[4] = 7 A[5] = 4there are four inversions:
(1,2) (1,3) (1,5) (4,5)so the function should return 4.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 1 minutes
Notes
not defined yet
Code: 01:17:06 UTC,
java,
autosave
Code: 01:17:16 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
-*- coding:utf-8 -*-
# &Author AnFany
# Lesson 99:Future training
# P 99.4 ArrayInversionCount
def solution_direct(A):
"""
返回数组A中逆序索引对的个数
时间复杂度O(N**2)
:param A: 数组
:return: 逆序索引对的个数
"""
return len([0 for i in range(len(A)) for j in range(i, len(A)) if A[i] > A[j]])
def merge(a):
"""
实现归并排序
:param a:数组
:return:逆序索引对的个数
"""
# 总的逆序索引对的个数
length = len(a)
if length <= 1:
return a, 0
# 分割点
middle = length // 2
# 左边
left_list, left_count = merge(a[: middle])
# 右边
right_list, right_count = merge(a[middle:])
# 左右之和
count = left_count + right_count
# 合并在一起的序列,也就是排序后的系列
sorted_list = []
# 合并时候的逆序数
while len(left_list) and len(right_list):
if left_list[0] > right_list[0]:
len_left = len(left_list)
count += len_left
small = right_list.pop(0)
sorted_list.append(small)
else:
small = left_list.pop(0)
sorted_list.append(small)
if left_list:
sorted_list += left_list
else:
sorted_list += right_list
return sorted_list, count
def solution(A):
"""
返回数组A中逆序索引对的个数
利用归并排序的思想,最终的逆序数对的个数=左序列排完序得到的逆序数+右序列排完序得到的逆序数+合并左右得到的逆序数
其实所有的逆序数归根结底都是合并左右得来的逆序数
时间复杂度:O(N*log(N))
:param A: 数组
:return: 逆序索引对的个数
"""
length = len(A)
if length <= 1:
return 0
count = merge(A)[1]
if count > 1e9:
return -1
return count
Code: 01:17:18 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
-*- coding:utf-8 -*-
# &Author AnFany
# Lesson 99:Future training
# P 99.4 ArrayInversionCount
def merge(a):
"""
实现归并排序
:param a:数组
:return:逆序索引对的个数
"""
# 总的逆序索引对的个数
length = len(a)
if length <= 1:
return a, 0
# 分割点
middle = length // 2
# 左边
left_list, left_count = merge(a[: middle])
# 右边
right_list, right_count = merge(a[middle:])
# 左右之和
count = left_count + right_count
# 合并在一起的序列,也就是排序后的系列
sorted_list = []
# 合并时候的逆序数
while len(left_list) and len(right_list):
if left_list[0] > right_list[0]:
len_left = len(left_list)
count += len_left
small = right_list.pop(0)
sorted_list.append(small)
else:
small = left_list.pop(0)
sorted_list.append(small)
if left_list:
sorted_list += left_list
else:
sorted_list += right_list
return sorted_list, count
def solution(A):
"""
返回数组A中逆序索引对的个数
利用归并排序的思想,最终的逆序数对的个数=左序列排完序得到的逆序数+右序列排完序得到的逆序数+合并左右得到的逆序数
其实所有的逆序数归根结底都是合并左右得来的逆序数
时间复杂度:O(N*log(N))
:param A: 数组
:return: 逆序索引对的个数
"""
length = len(A)
if length <= 1:
return 0
count = merge(A)[1]
if count > 1e9:
return -1
return count
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last): File "exec.py", line 129, in <module> main() File "exec.py", line 70, in main sol = __import__('solution') File "/tmp/solution.py", line 4 -*- coding\uff1autf-8 -*- ^ IndentationError: unexpected indent
Code: 01:17:26 UTC,
py,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 99:Future training
# P 99.4 ArrayInversionCount
def merge(a):
"""
实现归并排序
:param a:数组
:return:逆序索引对的个数
"""
# 总的逆序索引对的个数
length = len(a)
if length <= 1:
return a, 0
# 分割点
middle = length // 2
# 左边
left_list, left_count = merge(a[: middle])
# 右边
right_list, right_count = merge(a[middle:])
# 左右之和
count = left_count + right_count
# 合并在一起的序列,也就是排序后的系列
sorted_list = []
# 合并时候的逆序数
while len(left_list) and len(right_list):
if left_list[0] > right_list[0]:
len_left = len(left_list)
count += len_left
small = right_list.pop(0)
sorted_list.append(small)
else:
small = left_list.pop(0)
sorted_list.append(small)
if left_list:
sorted_list += left_list
else:
sorted_list += right_list
return sorted_list, count
def solution(A):
"""
返回数组A中逆序索引对的个数
利用归并排序的思想,最终的逆序数对的个数=左序列排完序得到的逆序数+右序列排完序得到的逆序数+合并左右得到的逆序数
其实所有的逆序数归根结底都是合并左右得来的逆序数
时间复杂度:O(N*log(N))
:param A: 数组
:return: 逆序索引对的个数
"""
length = len(A)
if length <= 1:
return 0
count = merge(A)[1]
if count > 1e9:
return -1
return count
Analysis
Code: 01:17:29 UTC,
py,
final,
score: 
100
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 99:Future training
# P 99.4 ArrayInversionCount
def merge(a):
"""
实现归并排序
:param a:数组
:return:逆序索引对的个数
"""
# 总的逆序索引对的个数
length = len(a)
if length <= 1:
return a, 0
# 分割点
middle = length // 2
# 左边
left_list, left_count = merge(a[: middle])
# 右边
right_list, right_count = merge(a[middle:])
# 左右之和
count = left_count + right_count
# 合并在一起的序列,也就是排序后的系列
sorted_list = []
# 合并时候的逆序数
while len(left_list) and len(right_list):
if left_list[0] > right_list[0]:
len_left = len(left_list)
count += len_left
small = right_list.pop(0)
sorted_list.append(small)
else:
small = left_list.pop(0)
sorted_list.append(small)
if left_list:
sorted_list += left_list
else:
sorted_list += right_list
return sorted_list, count
def solution(A):
"""
返回数组A中逆序索引对的个数
利用归并排序的思想,最终的逆序数对的个数=左序列排完序得到的逆序数+右序列排完序得到的逆序数+合并左右得到的逆序数
其实所有的逆序数归根结底都是合并左右得来的逆序数
时间复杂度:O(N*log(N))
:param A: 数组
:return: 逆序索引对的个数
"""
length = len(A)
if length <= 1:
return 0
count = merge(A)[1]
if count > 1e9:
return -1
return count
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Correctness tests
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
1.
0.040 s
OK