`

Counting inversions in an array

 
阅读更多

Count the number of inversion pairs in an array of n numbers.

       An inversion pair is defined as following: -

           If i < j and arr[i] > arr[j] then (arr[i], arr[j]) is called inversion pair

 

Solution 1:

This is almost normal merge sort, the whole magic is hidden in merge function. Note that while sorting algorithm remove inversions. While merging algorithm counts number of removed inversions (sorted out one might say).

The only moment when inversions are removed is when algorithm takes element from the right side of an array and merge it to the main array. The number of inversions removed by this operation is the number of elements left from the the left array to be merged.

Time Complexity: O(NlogN)

long merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, count = 0;
    while (i < left.length || j < right.length) {
        if (i == left.length) {
            arr[i+j] = right[j];
            j++;
        } else if (j == right.length) {
            arr[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            arr[i+j] = left[i];
            i++;                
        } else {
            arr[i+j] = right[j];
            count += left.length-i;
            j++;
        }
    }
    return count;
}

long invCount(int[] arr) {
    if (arr.length < 2)
        return 0;

    int m = (arr.length + 1) / 2;
    int left[] = Arrays.copyOfRange(arr, 0, m);
    int right[] = Arrays.copyOfRange(arr, m, arr.length);

    return invCount(left) + invCount(right) + merge(arr, left, right);
}

 

Solution 2:

其实这是个O(N^2)的解法,因为从数组中移除元素需要O(N)的时间复杂度。

  1. Merge sort array A and create a copy (array B)
  2. Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.

    2a. accumulate the number of inversions to counter variable num_inversions.

    2b. remove A[1] from array A and also from its corresponding position in array B

  3. rerun from step 2 until there are no more elements in A.

Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)

1: Merge sort and copy to array B

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: Take A[1] and binary search to find it in array B

A[1] = 6

B = (1, 2, 3, 6, 8, 9, 12, 14)

6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).

2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).

A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: Rerun from step 2 on the new A and B arrays.

A[1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)

Continuing in this vein will give us the total number of inversions for array A once the loop is complete.

Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).

 

References:
http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

http://www.geeksforgeeks.org/counting-inversions/

http://stackoverflow.com/questions/337664/counting-inversions-in-an-array?lq=1

分享到:
评论

相关推荐

    Standard Practices for Cycle Counting in Fatigue Analysis E1049

    These practices are a compilation of acceptable proce- dures for cycle-counting methods employed in fatigue analysis. This standard does not intend to recommend a particular method.

    Algorithm Design

    根据提供的文件信息,我们可以推断出这是一本关于算法设计的教材的相关出版信息。尽管页面内容部分并未提供具体的章节或内容细节,但基于标题“Algorithm Design”和描述“UCLA class: Algorithm Design”,我们可以...

    Counting Objects in C++

    标题"Counting Objects in C++"所指的就是如何在C++程序中实现一个机制来统计特定类实例的数量。描述中提到,这个过程简单但微妙,需要在类的构造函数和析构函数中分别增加和减少计数器,并提供一个静态成员函数来...

    Multi-Source Multi-Scale Counting in Extremely Dense Crowd Images

    这篇文章的标题是《Multi-Source Multi-Scale Counting in Extremely Dense Crowd Images》,其主要内容是介绍了一种在极密集的人群图像中利用多重信息源和多尺度分析来计算人数估计的方法。这一技术在计算机视觉...

    Coding Interview In Java

    8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 ...

    yolov8系列--Real time people counting system in computer vis.zip

    在计算机视觉领域,实时人数计数系统是一种广泛应用的技术,它涉及到图像处理、深度学习和人工智能等多个方面的知识。本文将深入探讨YoloV8在构建实时人流量统计系统中的作用及其相关技术。 首先,Yolo(You Only ...

    Tag Counting and Monitoring in Large-Scale RFID Systems

    ### 大规模RFID系统中的标签计数与监控 #### 引言 随着技术的不断发展,射频识别(RFID)技术已经广泛应用于各种场景之中,包括但不限于库存管理、物流追踪以及安全监控等领域。RFID系统的核心优势在于其能够实现...

    Redefinition of the Kilogram and Determination of an Exact Value of the Avogadro Constant by Counting Atoms in Carbon Onion

    本文探讨了利用碳洋葱重新定义千克单位,以及在此基础上确定阿伏伽德罗常数(Avogadro constant)精确值的方法。文章首先介绍了质量单位在宏观尺度(千克)和原子尺度(原子质量单位)上定义的差异,并指出了两者...

    Function Point Counting Practices Manual4.2.1

    The use of function points, as a measure of the functional size of software, has grown in the past decade from a few interested organizations to an impressive list of organizations worldwide. ...

    source统计工具Counting

    "Source统计工具Counting"是一款专门用于分析编程源代码的实用工具,它的主要功能是统计源代码中的有效行、空行以及注释行的数量。在软件开发和维护过程中,这样的统计信息对于理解代码规模、复杂度和维护性具有重要...

    [iFPUG] Function Point Counting Practices Manual R4.2.1-2005.pdf

    , as a measure of the functional size of software, has grown in the past decade from a few interested organizations to an impressive list of organizations worldwide. The IFPUG function point ...

    An Introduction to Programming in Emacs Lisp

    - **标题**:“An Introduction to Programming in Emacs Lisp”(Emacs Lisp编程入门) - **描述**:该资源是基于Emacs官方文档的重编版本,旨在提供更易阅读的字体样式。 #### 知识点详解 ##### 1. Emacs Lisp...

    An Occlusion Sensitive Method for People Counting in Crowded Situations

    We present an occlusion sensitive method for counting crowded people in congested situations to reduce the occurrences of catastrophic stampedes and crammed events. First, we adopt the Frame ...

    3D people counting implementation guide

    《3D人员计数实施指南》是针对使用毫米波雷达技术进行三维人体计数的软件实现文档,由德州仪器(Texas Instruments)发布。本指南详细介绍了如何设置演示系统,以及利用SDK组件进行3D人员计数的具体步骤。...

    53958727box-counting.zip

    在IT领域,分形盒维数(Box-Counting Dimension)是研究复杂几何形状和结构的一种重要工具,尤其在图像处理、数据建模和复杂网络分析中有着广泛的应用。本项目"53958727box-counting.zip"显然是针对1D、2D、3D空间中...

    The Pleasures of Counting 1996

    The Pleasures of Counting 1996 © Cambridge University Press 1996

    Counting.exe

    《代码行统计工具Counting.exe详解》 在软件开发过程中,了解代码的规模是至关重要的。这不仅可以评估项目的复杂性,还可以为项目管理和资源分配提供参考。Counting.exe是一款高效实用的代码行统计工具,它支持多种...

    counting 代码行数统计

    标题中的“counting 代码行数统计”指的是在软件开发过程中对源代码文件中的代码行进行计数的活动。这通常用于评估项目的工作量、跟踪开发进度或比较不同版本的代码变化。代码行数统计可以帮助开发者理解代码的复杂...

Global site tag (gtag.js) - Google Analytics