统计右侧较小元素 - 算法解析与代码实现

源内容（英文）

给定一个由不同整数组成的未排序数组 arr[]，请构建另一个数组 countSmaller[]，使得 countSmaller[i] 包含数组中每个元素 arr[i] 右侧较小元素的计数。

示例：

> 输入： arr[] = [12, 1, 2, 3, 0, 11, 4]

> 输出： [6, 1, 1, 1, 0, 1, 0]

>

> 输入： arr[] = [5, 4, 3, 2, 1]

> 输出： [4, 3, 2, 1, 0]

>

> 输入： arr[] = [1, 2, 3, 4, 5]

> 输出： [0, 0, 0, 0, 0]
在线练习题目!

目录

• [朴素方法] 使用嵌套循环 – O(n*n) 时间复杂度和 O(n) 空间复杂度
• [期望方法] 使用归并排序 – O(nlogn) 时间复杂度和 O(n) 空间复杂度

[朴素方法] 使用嵌套循环 – O(n*n) 时间复杂度和 O(n) 空间复杂度

> 这个思路是使用嵌套循环，对于每一个元素，我们检查其右侧有多少个元素比它小。

C++

    #include 
    #include 
    using namespace std;

    vector constructLowerArray(vector& arr) {
        int n = arr.size();
        vector countSmaller(n, 0);
        int i, j;

        // 检查每个元素右侧有多少个比它小的元素
        for (i = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) {
                if (arr[j] < arr[i])
                    countSmaller[i]++;
            }
        }
        return countSmaller;
    }

    // 打印数组的辅助函数
    void printArray(vector& arr) {
        int n = arr.size();
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << "
";
    }

    // 主函数
    int main() {
        vector arr = {12, 1, 2, 3, 0, 11, 4};

        vector low = constructLowerArray(arr);
        printArray(low);

        return 0;
    }
    

Java

    import java.util.*;

    class Main {
        static ArrayList constructLowerArray(int[] arr) {
            int n = arr.length;
            ArrayList countSmaller = new ArrayList(Collections.nCopies(n, 0));

            // 检查每个元素右侧有多少个比它小的元素
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (arr[j] < arr[i])
                        countSmaller.set(i, countSmaller.get(i) + 1);
                }
            }
            return countSmaller;
        }

        // 打印数组的辅助函数
        static void printArray(ArrayList arr) {
            for (int x : arr)
                System.out.print(x + " ");
            System.out.println();
        }

        public static void main(String[] args) {
            int[] arr = {12, 1, 2, 3, 0, 11, 4};

            ArrayList low = constructLowerArray(arr);
            printArray(low);
        }
    }
    

Python

    def constructLowerArray(arr):
        n = len(arr)
        countSmaller = [0] * n

        # 检查每个元素右侧有多少个比它小的元素
        for i in range(n):
            for j in range(i + 1, n):
                if arr[j] < arr[i]:
                    countSmaller[i] += 1

        return countSmaller

    # 打印数组的辅助函数
    def printArray(arr):
        for x in arr:
            print(x, end=" ")
        print()

    if __name__ =="__main__":
        arr = [12, 1, 2, 3, 0, 11, 4]
        
        low = constructLowerArray(arr)
        printArray(low)
    

C#

    using System;
    using System.Collections.Generic;

    class Program {
        static List ConstructLowerArray(int[] arr) {
            int n = arr.Length;
            List countSmaller = new List(new int[n]);

            // 检查每个元素右侧有多少个比它小的元素
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (arr[j] < arr[i])
                        countSmaller[i]++;
                }
            }
            return countSmaller;
        }

        // 打印数组的辅助函数
        static void PrintArray(List arr) {
            foreach (int x in arr)
                Console.Write(x + " ");
            Console.WriteLine();
        }

        static void Main() {
            int[] arr = {12, 1, 2, 3, 0, 11, 4};

            List low = ConstructLowerArray(arr);
            PrintArray(low);
        }
    }
    

JavaScript

    function constructLowerArray(arr) {
        let n = arr.length;
        let countSmaller = new Array(n).fill(0);

        // 检查每个元素右侧有多少个比它小的元素
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                if (arr[j] < arr[i])
                    countSmaller[i]++;
            }
        }
        return countSmaller;
    }

    // 打印数组的辅助函数
    function printArray(arr) {
        console.log(arr.join(" "));
    }

    // 主函数
    let arr = [12, 1, 2, 3, 0, 11, 4];

    let low = constructLowerArray(arr);
    printArray(low);
    

输出

6 1 1 1 0 1 0

[期望方法] 使用归并排序 – O(nlogn) 时间复杂度和 O(n) 空间复杂度

…