Dada una array arr[] de enteros positivos, la tarea es clasificar la array en orden decreciente de conteo de bits establecidos en representaciones binarias de elementos de la array.
Para los números enteros que tienen el mismo número de bits establecidos en su representación binaria, clasifíquelos de acuerdo con su posición en la array original, es decir, una clasificación estable. Por ejemplo, si la array de entrada es {3, 5}, la array de salida también debe ser {3, 5}. Tenga en cuenta que tanto el 3 como el 5 tienen el mismo conjunto de bits.
Ejemplos:
Entrada: arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32}
Salida: 15 7 5 3 9 6 2 4 32
Los enteros en su representación binaria son:
15 – 1111
7 – 0111
5 – 0101
3 – 0011
9 – 1001
6 – 0110
2 – 0010
4 – 0100
32 – 10000
Por lo tanto, el orden ordenado no creciente es:
{15, 7, 5, 3, 9, 6, 2, 4, 32}
Entrada: arr[] = {1, 2, 3, 4, 5, 6};
Salida: 3 5 6 1 2 4
Enfoque: Ya hemos discutido el método de clasificación basado en el recuento de bits establecido en la sección anterior con varios métodos. Esta publicación contiene implementación usando mapas .
Como sabemos, un mapa/multimapa almacena datos de manera ordenada. Entonces, si almacenamos (32 – countsetbits(arr[i])) para un arr[i] en el mapa, entonces la salida saldrá en orden decreciente del conteo de bits establecido, que es la salida deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// function to sort the array according
// to the number of set bits in elements
void sortArr(int arr[], int n)
{
multimap<int, int> map;
for (int i = 0; i < n; i++) {
int count = 0;
int k = arr[i];
// Counting no of setBits in arr[i]
while (k) {
k = k & k - 1;
count++;
}
// The count is subtracted from 32
// because the result needs
// to be in descending order
map.insert(make_pair(32 - count, arr[i]));
}
// Printing the numbers in descending
// order of set bit count
for (auto it = map.begin(); it != map.end(); it++) {
cout << (*it).second << " ";
}
}
// Driver code
int main()
{
int arr[] = { 5, 2, 3, 9, 4, 6, 7, 15, 32 };
int n = sizeof(arr) / sizeof(arr[0]);
sortArr(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
// Compare class to sort 2d array
// by 1st value
class Compare implements Comparator<int[]> {
@Override public int compare(int[] a, int[] b)
{
return a[0] - b[0];
}
}
class GFG {
// function to sort the array according
// to the number of set bits in elements
static void sortArr(int[] arr, int n)
{
int[][] map = new int[n][2];
for (int i = 0; i < n; i++) {
int count = 0;
int k = arr[i];
// Counting no of setBits in arr[i]
while (k > 0) {
k = k & k - 1;
count++;
}
// The count is subtracted from 32
// because the result needs
// to be in descending order
map[i][0] = 32 - count;
map[i][1] = arr[i];
}
Arrays.sort(map, new Compare());
// Printing the numbers in descending
// order of set bit count
for (int i = 0; i < map.length; i++) {
System.out.print(map[i][1] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 5, 2, 3, 9, 4, 6, 7, 15, 32 };
int n = arr.length;
sortArr(arr, n);
}
}
// This code is contributed by phasing17
Python3
# Python3 implementation of the approach # function to sort the array according # to the number of set bits in elements def sortArr(arr, n): mp = [] for i in range( n): count = 0 k = arr[i] # Counting no of setBits in arr[i] while (k): k = k & k - 1 count += 1 # The count is subtracted from 32 # because the result needs # to be in descending order mp.append((32 - count, arr[i])) # Printing the numbers in descending # order of set bit count mp.sort(key = lambda x: x[0]) for it in mp: print(it[1], end= " ") # Driver code if __name__ == "__main__": arr = [ 5, 2, 3, 9, 4, 6, 7, 15, 32 ] n = len(arr) sortArr(arr, n) # This code is contributed by chitranayal
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
// Compare class to sort 2d array
// by 1st value
class CompareArr : Comparer<int[]> {
public override int Compare(int[] a, int[] b)
{
return a[0] - b[0];
}
}
class GFG
{
// function to sort the array according
// to the number of set bits in elements
static void sortArr(int[] arr, int n)
{
int[][] map = new int[n][];
for (int i = 0; i < n; i++) {
map[i] = new int[2];
int count = 0;
int k = arr[i];
// Counting no of setBits in arr[i]
while (k > 0) {
k = k & k - 1;
count++;
}
// The count is subtracted from 32
// because the result needs
// to be in descending order
map[i][0] = 32 - count;
map[i][1] = arr[i];
}
Array.Sort(map, new CompareArr());
// Printing the numbers in descending
// order of set bit count
for (int i = 0; i < map.Length; i++) {
Console.Write(map[i][1] + " ");
}
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 5, 2, 3, 9, 4, 6, 7, 15, 32 };
int n = arr.Length;
sortArr(arr, n);
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript implementation of the approach
// function to sort the array according
// to the number of set bits in elements
function sortArr(arr,n)
{
let map=[];
for (let i = 0; i < n; i++) {
let count = 0;
let k = arr[i];
// Counting no of setBits in arr[i]
while (k) {
k = k & k - 1;
count++;
}
// The count is subtracted from 32
// because the result needs
// to be in descending order
map.push([32 - count, arr[i]]);
}
map.sort(function(a,b){return a[0]-b[0];});
// Printing the numbers in descending
// order of set bit count
for (let i=0;i<map.length;i++) {
document.write(map[i][1]+" ");
}
}
// Driver code
let arr=[5, 2, 3, 9, 4, 6, 7, 15, 32 ];
let n=arr.length;
sortArr(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
15 7 5 3 9 6 2 4 32
Complejidad de tiempo: O(n * log n)
Espacio Auxiliar: O(n)