Nombre d’éléments plus petits sur le côté droit de chaque élément d’un tableau à l’aide du tri par fusion

using System;

using System.Collections.Generic;

class GFG

{

    

    

    public class Item

    {

        public int val;

        public int index;

        public Item(int val, int index)

        {

            this.val = val;

            this.index = index;

        }

    }

    

    

    public List<int> countSmall(int[] A)

    {

        int len = A.Length;

        Item[] items = new Item[len];

        for (int i = 0; i < len; i++)

        {

            items[i] = new Item(A[i], i);

        }

        int[] count = new int[len];

        mergeSort(items, 0, len - 1, count);

        List<int> res = new List<int>();

        foreach (int i in count)

        {

            res.Add(i);

        }

        return res;

    }

    

    private void mergeSort(Item[] items,

                        int low, int high,

                        int[] count)

    {

        if (low >= high)

        {

            return;

        }

        int mid = low + (high - low) / 2;

        mergeSort(items, low, mid, count);

        mergeSort(items, mid + 1, high, count);

        merge(items, low, mid, mid + 1, high, count);

    }

    

    

    private void merge(Item[] items, int low,

                    int lowEnd, int high,

                    int highEnd, int[] count)

    {

        int m = highEnd - low + 1;

        Item[] sorted = new Item[m];

        int rightCounter = 0;

        int lowPtr = low, highPtr = high;

        int index = 0;

        

        

        

        while (lowPtr <= lowEnd && highPtr <= highEnd)

        {

            if (items[lowPtr].val > items[highPtr].val)

            {

                rightCounter++;

                sorted[index++] = items[highPtr++];

            }

            else

            {

                count[items[lowPtr].index] += rightCounter;

                sorted[index++] = items[lowPtr++];

            }

        }

        

        

        

        while (lowPtr <= lowEnd)

        {

            count[items[lowPtr].index] += rightCounter;

            sorted[index++] = items[lowPtr++];

        }

        

        

        

        while (highPtr <= highEnd)

        {

            sorted[index++] = items[highPtr++];

        }

        Array.Copy(sorted, 0, items, low, m);

    }

    

    

    void printArray(List<int> countList)

    {

        foreach (int i in countList)

            Console.Write(i + " ");

        Console.WriteLine("");

    }

    

    public static void Main(String[] args)

    {

        GFG cntSmall = new GFG();

        int []arr = { 10, 9, 5, 2, 7, 6, 11, 0, 2 };

        int n = arr.Length;

        List<int> countList

            = cntSmall.countSmall(arr);

        cntSmall.printArray(countList);

    }

}

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut