Ordenar array según el módulo de sus valores con sus frecuencias

Dada una array arr que contiene N enteros positivos, ordénelos según el módulo creciente de sus valores con sus frecuencias.

Ejemplo:

Entrada: arr[]={1, 1, 5, 3, 2, 3, 3, 3, 4, 5, 4, 5} Salida: 2 4 4 1 1 5 5 5 3 3 3
3 Explicación 
:
Los elementos son ordenados en el siguiente orden:
2 % frecuencia(2) = 2 % 1 = 0
4 % frecuencia(4) = 4 % 2 = 0
1 % frecuencia(1) = 1 % 2 = 1
5 % frecuencia(5) = 5 % 3 = 2
3 % frecuencia(4) = 3 % 4 = 3

Entrada: arr[]={2, 9, 8, 2, 8, 9, 2, 8, 5}
Salida: 5 9 9 2 2 2 8 8 8 

Enfoque: para resolver esta pregunta, almacene las frecuencias de cada número en un mapa y luego cree un comparador personalizado, que hará la clasificación. Esa función de comparación aceptará dos valores enteros, digamos A y B como parámetros y la condición en ese comparador para ordenar la array es:

(A % frecuencia(A)) > (B % frecuencia(B))

A continuación se muestra la implementación del enfoque anterior.

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the numbers in an array
// according to the modulus of their values
// with their frequencies
void customSort(vector<int>& arr)
{
 
    // Map to store
    // the frequencies of each number
    unordered_map<int, int> freq;
    for (auto x : arr) {
        freq[x]++;
    }
 
    // Sorting them using
    // a custom comparator
    sort(arr.begin(), arr.end(),
         [&](int A, int B) {
             if (A % freq[A] == B % freq[B]) {
                 return A < B;
             }
             return A % freq[A] < B % freq[B];
         });
 
    // Printing the numbers
    for (auto x : arr) {
        cout << x << ' ';
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 9, 8, 2, 8,
                        9, 2, 8, 5 };
    customSort(arr);
}

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Function to sort the numbers in an array
// according to the modulus of their values
// with their frequencies
static void customSort(Integer []arr)
{
 
    // Map to store
    // the frequencies of each number
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
    for (int x : arr) {
        if(freq.containsKey(x)){
            freq.put(x, freq.get(x)+1);
        }
        else{
            freq.put(x, 1);
        }
    }
 
    // Sorting them using
    // a custom comparator
    Arrays.sort(arr, new Comparator<Integer>(){
  
        @Override
        public int compare(Integer a, Integer b)
        {
            // If both are odd or even
            // then sorting in increasing order
            if ((a % freq.get(a)) == (b % freq.get(b))) {
                return a < b?-1:1;
            }
  
            // Sorting on the basis of last bit if
            // if one is odd and the other one is even
            return ((a % freq.get(a)) < (b % freq.get(b)))?-1:1;
        }
          
    });
    // Printing the numbers
    for (int x : arr) {
        System.out.print(x +" ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    Integer []arr = { 2, 9, 8, 2, 8,
                        9, 2, 8, 5 };
    customSort(arr);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 code for the above approach
 
# Function to sort the numbers in an array
# according to the modulus of their values
# with their frequencies
from collections import OrderedDict
from filecmp import cmp
from functools import cmp_to_key
 
freq = {}
 
def custom_sort(A, B):
     
    global freq
 
    if (A % freq[A] == B % freq[B]):
        return A - B
 
    return ((A % freq[A]) - (B % freq[B]))
 
def arr_sort(a,b):
    return a[0] - b[0]
 
def customSort(arr):
 
    global freq
     
    # Map to store
    # the frequencies of each number
    for x in arr :
        if x in freq:
            freq[x] = freq[x] + 1
        else:
            freq[x] = 1
 
    freq = OrderedDict(sorted(freq.items(),key = cmp_to_key(arr_sort)))
 
    # Sorting them using
    # a custom comparator
    arr.sort(key = cmp_to_key(custom_sort))
 
    # Printing the numbers
    for x in arr:
        print(x,end = ' ')
 
# Driver Code
arr = [2, 9, 8, 2, 8, 9, 2, 8, 5]
customSort(arr)
 
# This code is contributed by shinjanpatra

// C# code for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to sort the numbers in an array
    // according to the modulus of their values
    // with their frequencies
    static void customSort(int[] arr)
    {
 
        // Map to store
        // the frequencies of each number
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int x in arr)
        {
            if (freq.ContainsKey(x))
            {
                freq[x] += 1;
            }
            else
            {
                freq[x] = 1;
            }
        }
 
        // Sorting them using
        // a custom comparator
        Array.Sort(arr, (a, b)
             =>
        {
            // If both are odd or even
            // then sorting in increasing order
            if ((a % freq[a]) == (b % freq[b]))
            {
                return a < b ? -1 : 1;
            }
 
            // Sorting on the basis of last bit if
            // if one is odd and the other one is even
            return ((a % freq[a]) < (b % freq[b])) ? -1 : 1;
        });
        // Printing the numbers
 
        foreach (int x in arr)
        {
            Console.Write(x + " ");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 2, 9, 8, 2, 8,
                        9, 2, 8, 5 };
        customSort(arr);
    }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
// Javascript code for the above approach
 
// Function to sort the numbers in an array
// according to the modulus of their values
// with their frequencies
function customSort(arr) {
 
    // Map to store
    // the frequencies of each number
    let freq = new Map();
    for (x of arr) {
        if (freq.has(x)) {
            freq.set(x, freq.get(x) + 1)
        } else {
            freq.set(x, 1)
        }
    }
 
    freq = new Map([...freq].sort((a, b) => a[0] - b[0]));
 
 
    // Sorting them using
    // a custom comparator
    arr.sort((A, B) => {
        if (A % freq.get(A) == B % freq.get(B)) {
            return A - B;
        }
 
        return ((A % freq.get(A)) - (B % freq.get(B)));
    });
 
    // Printing the numbers
    for (x of arr) {
        document.write(x + ' ');
    }
}
 
// Driver Code
let arr = [2, 9, 8, 2, 8, 9, 2, 8, 5];
customSort(arr);
 
// This code is contributed by gfgking.
</script>

5 9 9 2 2 2 8 8 8 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)