Dada una array de enteros positivos, ordene la array en orden decreciente de conteo de bits establecidos en representaciones binarias de elementos de array. Para los números enteros que tienen el mismo número de bits establecidos en su representación binaria, clasifíquelos según 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 debería ser {3, 5}. Tenga en cuenta que tanto el 3 como el 5 tienen el mismo conjunto de bits.
Ejemplos:
Input: arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32};
Output: 15 7 5 3 9 6 2 4 32
Explanation:
The integers in their binary representation are:
15 -1111
7 -0111
5 -0101
3 -0011
9 -1001
6 -0110
2 -0010
4- -0100
32 -10000
hence the non-increasing sorted order is:
{15}, {7}, {5, 3, 9, 6}, {2, 4, 32}
Input: arr[] = {1, 2, 3, 4, 5, 6};
Output: 3 5 6 1 2 4
Explanation:
3 - 0011
5 - 0101
6 - 0110
1 - 0001
2 - 0010
4 - 0100
hence the non-increasing sorted order is
{3, 5, 6}, {1, 2, 4}
Método 1: Sencillo
- Cree una array auxiliar y almacene los recuentos de bits establecidos de todos los enteros en la array auxiliar
- Ordene simultáneamente ambas arrays de acuerdo con el orden no creciente de la array auxiliar. (Tenga en cuenta que necesitamos usar un algoritmo de clasificación estable)
Before sort:
int arr[] = {1, 2, 3, 4, 5, 6};
int aux[] = {1, 1, 2, 1, 2, 2}
After sort:
arr = {3, 5, 6, 1, 2, 4}
aux = {2, 2, 2, 1, 1, 1}
Implementación:
C++
// C++ program to implement simple approach to sort an array
// according to count of set bits.
#include <bits/stdc++.h>
using namespace std;
// a utility function that returns total set bits count in an integer
int countBits(int a)
{
int count = 0;
while (a) {
if (a & 1)
count += 1;
a = a >> 1;
}
return count;
}
// Function to simultaneously sort both arrays using insertion sort
// https://www.geeksforgeeks.org/insertion-sort/ )
void insertionSort(int arr[], int aux[], int n)
{
for (int i = 1; i < n; i++) {
// use 2 keys because we need to sort both arrays simultaneously
int key1 = aux[i];
int key2 = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] and aux[0..i-1],
// such that elements of aux[0..i-1] are greater
// than key1, to one position ahead of their current
// position
while (j >= 0 && aux[j] < key1) {
aux[j + 1] = aux[j];
arr[j + 1] = arr[j];
j = j - 1;
}
aux[j + 1] = key1;
arr[j + 1] = key2;
}
}
// Function to sort according to bit count using an auxiliary array
void sortBySetBitCount(int arr[], int n)
{
// Create an array and store count of set bits in it.
int aux[n];
for (int i = 0; i < n; i++)
aux[i] = countBits(arr[i]);
// Sort arr[] according to values in aux[]
insertionSort(arr, aux, n);
}
// Utility function to print an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
sortBySetBitCount(arr, n);
printArr(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to implement simple approach to sort an array
// according to count of set bits.
#include <stdio.h>
// a utility function that returns total set bits count in an integer
int countBits(int a)
{
int count = 0;
while (a) {
if (a & 1)
count += 1;
a = a >> 1;
}
return count;
}
// Function to simultaneously sort both arrays using insertion sort
// https://www.geeksforgeeks.org/insertion-sort/ )
void insertionSort(int arr[], int aux[], int n)
{
for (int i = 1; i < n; i++) {
// use 2 keys because we need to sort both arrays simultaneously
int key1 = aux[i];
int key2 = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] and aux[0..i-1],
// such that elements of aux[0..i-1] are greater
// than key1, to one position ahead of their current
// position
while (j >= 0 && aux[j] < key1) {
aux[j + 1] = aux[j];
arr[j + 1] = arr[j];
j = j - 1;
}
aux[j + 1] = key1;
arr[j + 1] = key2;
}
}
// Function to sort according to bit count using an auxiliary array
void sortBySetBitCount(int arr[], int n)
{
// Create an array and store count of set bits in it.
int aux[n];
for (int i = 0; i < n; i++)
aux[i] = countBits(arr[i]);
// Sort arr[] according to values in aux[]
insertionSort(arr, aux, n);
}
// Utility function to print an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
sortBySetBitCount(arr, n);
printArr(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to implement simple approach to sort an
// array according to count of set bits.
import java.io.*;
class GFG {
// utility function that returns total set bits count in an integer
static int countBits(int a)
{
int count = 0;
while (a > 0) {
if ((a & 1) > 0)
count += 1;
a = a >> 1;
}
return count;
}
// Function to simultaneously sort both arrays using insertion sort
// (https://www.geeksforgeeks.org/insertion-sort/ )
static void insertionSort(int arr[], int aux[], int n)
{
for (int i = 1; i < n; i++) {
// use 2 keys because we need to sort both
// arrays simultaneously
int key1 = aux[i];
int key2 = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] and aux[0..i-1],
// such that elements of aux[0..i-1] are greater
// than key1, to one position ahead of their
// current position
while (j >= 0 && aux[j] < key1) {
aux[j + 1] = aux[j];
arr[j + 1] = arr[j];
j = j - 1;
}
aux[j + 1] = key1;
arr[j + 1] = key2;
}
}
// Function to sort according to bit count using an auxiliary array
static void sortBySetBitCount(int arr[], int n)
{
// Create an array and store count of set bits in it.
int aux[] = new int[n];
for (int i = 0; i < n; i++)
aux[i] = countBits(arr[i]);
// Sort arr[] according to values in aux[]
insertionSort(arr, aux, n);
}
// Utility function to print an array
static void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = arr.length;
sortBySetBitCount(arr, n);
printArr(arr, n);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python 3 program to implement simple approach to sort # an array according to count of set bits. # a utility function that returns total set bits # count in an integer def countBits(a): count = 0 while (a): if (a & 1): count+= 1 a = a>>1 return count # Function to simultaneously sort both arrays # using insertion sort # ( http:#quiz.geeksforgeeks.org/insertion-sort/ ) def insertionSort(arr,aux, n): for i in range(1,n,1): # use 2 keys because we need to sort both # arrays simultaneously key1 = aux[i] key2 = arr[i] j = i-1 # Move elements of arr[0..i-1] and aux[0..i-1], # such that elements of aux[0..i-1] are # greater than key1, to one position ahead # of their current position */ while (j >= 0 and aux[j] < key1): aux[j+1] = aux[j] arr[j+1] = arr[j] j = j-1 aux[j+1] = key1 arr[j+1] = key2 # Function to sort according to bit count using # an auxiliary array def sortBySetBitCount(arr, n): # Create an array and store count of # set bits in it. aux = [0 for i in range(n)] for i in range(0,n,1): aux[i] = countBits(arr[i]) # Sort arr[] according to values in aux[] insertionSort(arr, aux, n) # Utility function to print an array def printArr(arr, n): for i in range(0,n,1): print(arr[i],end = " ") # Driver Code if __name__ =='__main__': arr = [1, 2, 3, 4, 5, 6] n = len(arr) sortBySetBitCount(arr, n) printArr(arr, n) # This code is contributed by # Surendra_Gangwar
C#
// C# program to implement
// simple approach to sort
// an array according to
// count of set bits.
using System;
public class GFG
{
// a utility function that
// returns total set bits
// count in an integer
static int countBits(int a)
{
int count = 0;
while (a > 0)
{
if ((a & 1) > 0)
count += 1;
a = a >> 1;
}
return count;
}
// Function to simultaneously
// sort both arrays using
// insertion sort
// (https://www.geeksforgeeks.org/insertion-sort/ )
// Function to simultaneously
// sort both arrays using
// insertion sort
// (https://www.geeksforgeeks.org/insertion-sort/ )
static void insertionSort(int []arr,
int []aux, int n)
{
for (int i = 1; i < n; i++)
{
// use 2 keys because we
// need to sort both
// arrays simultaneously
int key1 = aux[i];
int key2 = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1]
and aux[0..i-1], such that
elements of aux[0..i-1] are
greater than key1, to one
position ahead of their current
position */
while (j >= 0 && aux[j] < key1)
{
aux[j + 1] = aux[j];
arr[j + 1] = arr[j];
j = j - 1;
}
aux[j + 1] = key1;
arr[j + 1] = key2;
}
}
// Function to sort according
// to bit count using an
// auxiliary array
static void sortBySetBitCount(int []arr,
int n)
{
// Create an array and
// store count of
// set bits in it.
int []aux = new int[n];
for (int i = 0; i < n; i++)
aux[i] = countBits(arr[i]);
// Sort arr[] according
// to values in aux[]
insertionSort(arr, aux, n);
}
// Utility function
// to print an array
static void printArr(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
static public void Main ()
{
int []arr = {1, 2, 3, 4, 5, 6};
int n = arr.Length;
sortBySetBitCount(arr, n);
printArr(arr, n);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to implement
// simple approach to sort
// an array according to
// count of set bits.
// a utility function that
// returns total set bits
// count in an integer
function countBits(a)
{
let count = 0;
while (a > 0)
{
if ((a & 1) > 0)
count+= 1;
a = a >> 1;
}
return count;
}
// Function to simultaneously
// sort both arrays using
// insertion sort
// (https://www.geeksforgeeks.org/insertion-sort/ )
function insertionSort(arr,aux,n)
{
for (let i = 1; i < n; i++)
{
// use 2 keys because we
// need to sort both
// arrays simultaneously
let key1 = aux[i];
let key2 = arr[i];
let j = i - 1;
/* Move elements of arr[0..i-1]
and aux[0..i-1], such that
elements of aux[0..i-1] are
greater than key1, to one
position ahead of their current
position */
while (j >= 0 && aux[j] < key1)
{
aux[j + 1] = aux[j];
arr[j + 1] = arr[j];
j = j - 1;
}
aux[j + 1] = key1;
arr[j + 1] = key2;
}
}
// Function to sort according
// to bit count using an
// auxiliary array
function sortBySetBitCount(arr,n)
{
// Create an array and
// store count of
// set bits in it.
let aux = new Array(n);
for (let i = 0; i < n; i++)
aux[i] = countBits(arr[i]);
// Sort arr[] according
// to values in aux[]
insertionSort(arr, aux, n);
}
// Utility function
// to print an array
function printArr(arr,n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr=[1, 2, 3, 4, 5, 6];
let n = arr.length;
sortBySetBitCount(arr, n);
printArr(arr, n);
// This code is contributed by unknown2108
</script>
Producción
3 5 6 1 2 4
Espacio auxiliar: O(n)
Complejidad temporal: O(n 2 )
Nota: La complejidad del tiempo se puede mejorar a O(nLogn) mediante el uso de un algoritmo de clasificación O(nlogn) estable.
Método 2: Usar std::sort()
Uso del comparador personalizado de std::sort para ordenar la array de acuerdo con el recuento de bits establecido
C++
// C++ program to sort an array according to count of set
// bits using std::sort()
#include <bits/stdc++.h>
using namespace std;
// a utility function that returns total set bits count in an integer
int countBits(int a)
{
int count = 0;
while (a) {
if (a & 1)
count += 1;
a = a >> 1;
}
return count;
}
// custom comparator of std::sort
int cmp(int a, int b)
{
int count1 = countBits(a);
int count2 = countBits(b);
// this takes care of the stability of sorting algorithm too
if (count1 <= count2)
return false;
return true;
}
// Function to sort according to bit count using std::sort
void sortBySetBitCount(int arr[], int n)
{
stable_sort(arr, arr + n, cmp);
}
// Utility function to print an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
sortBySetBitCount(arr, n);
printArr(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to sort an array according to count of set bits
// using std::sort()
#include <stdio.h>
// a utility function that returns total set bits count in an integer
int countBits(int a)
{
int count = 0;
while (a) {
if (a & 1)
count += 1;
a = a >> 1;
}
return count;
}
// custom comparator of std::sort
int cmp(int a, int b)
{
int count1 = countBits(a);
int count2 = countBits(b);
// this takes care of the stability of sorting algorithm too
if (count1 <= count2)
return false;
return true;
}
// Function to sort according to bit count using std::sort
void sortBySetBitCount(int arr[], int n)
{
stable_sort(arr, arr + n, cmp);
}
// Utility function to print an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
sortBySetBitCount(arr, n);
printArr(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to sort an array according to count of set
// bits using std::sort()
import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String[] args)
{
Integer arr[] = { 1, 2, 3, 4, 5, 6 };
int n = 6;
sortBySetBitCount(arr, n);
printArr(arr, n);
System.out.println();
}
private static void printArr(Integer[] arr, int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
private static Integer[] sortBySetBitCount(
Integer[] arr, int n)
{
Arrays.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1)
{
int c1 = Integer.bitCount(arg0);
int c2 = Integer.bitCount(arg1);
if (c1 <= c2)
return 1;
else
return -1;
}
});
return arr;
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Using custom comparator lambda function arr = [1, 2, 3, 4, 5, 6] # form a tuple with val, index n = len(arr) arr = [(arr[i], i) for i in range(n)] def countSetBits(val): cnt = 0 while val: cnt += val % 2 val = val//2 return cnt # first criteria to sort is number of set bits, # then the index sorted_arr = sorted(arr, key=lambda val: ( countSetBits(val[0]), n-val[1]), reverse=True) sorted_arr = [val[0] for val in sorted_arr] print(sorted_arr)
Javascript
<script>
// Javascript program to sort an array according to
// count of set bits using std::sort()
function printArr(arr,n)
{
// TODO Auto-generated method stub
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
function sortBySetBitCount(arr,n)
{
arr.sort(function(a,b){
c1 = Number(a.toString(2).split("").sort().join("")).toString().length;
c2 = Number(b.toString(2).split("").sort().join("")).toString().length;
return c2-c1;
})
}
let arr = [1, 2, 3, 4, 5, 6 ];
let n = 6;
sortBySetBitCount(arr, n);
printArr(arr, n);
document.write();
// This code is contributed by ab2127
</script>
Producción
3 5 6 1 2 4
Espacio auxiliar: O(1)
Complejidad temporal: O(n log n)
Método 3: Clasificación por conteo basada
Este problema se puede resolver en tiempo O(n). La idea es similar a ordenar por conteo.
Nota: Puede haber un mínimo de 1 conjunto de bits y solo un máximo de 31 conjuntos de bits en un número entero.
Pasos (suponiendo que un número entero ocupa 32 bits):
- Cree un vector «conteo» de tamaño 32. Cada celda de conteo, es decir, conteo[i], es otro vector que almacena todos los elementos cuyo conjunto de conteo de bits es i
- Recorra la array y haga lo siguiente para cada elemento:
- Cuente el número de bits de conjunto de este elemento. Que sea ‘setbitcount’
- cuenta[setbitcount].push_back(elemento)
- Recorra ‘contar’ de manera inversa (ya que necesitamos ordenar en orden no creciente) y modifique la array.
C++
// C++ program to sort an array according to
// count of set bits using std::sort()
#include <bits/stdc++.h>
using namespace std;
// a utility function that returns total set bits
// count in an integer
int countBits(int a)
{
int count = 0;
while (a)
{
if (a & 1 )
count+= 1;
a = a>>1;
}
return count;
}
// Function to sort according to bit count
// This function assumes that there are 32
// bits in an integer.
void sortBySetBitCount(int arr[],int n)
{
vector<vector<int> > count(32);
int setbitcount = 0;
for (int i=0; i<n; i++)
{
setbitcount = countBits(arr[i]);
count[setbitcount].push_back(arr[i]);
}
int j = 0; // Used as an index in final sorted array
// Traverse through all bit counts (Note that we
// sort array in decreasing order)
for (int i=31; i>=0; i--)
{
vector<int> v1 = count[i];
for (int i=0; i<v1.size(); i++)
arr[j++] = v1[i];
}
}
// Utility function to print an array
void printArr(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
sortBySetBitCount(arr, n);
printArr(arr, n);
return 0;
}
Java
// Java program to sort an
// array according to count
// of set bits using std::sort()
import java.util.*;
class GFG{
// a utility function that
// returns total set bits
// count in an integer
static int countBits(int a)
{
int count = 0;
while (a > 0)
{
if ((a & 1) > 0 )
count += 1;
a = a >> 1;
}
return count;
}
// Function to sort according to
// bit count. This function assumes
// that there are 32 bits in an integer.
static void sortBySetBitCount(int arr[],
int n)
{
Vector<Integer> []count =
new Vector[32];
for (int i = 0;
i < count.length; i++)
count[i] = new Vector<Integer>();
int setbitcount = 0;
for (int i = 0; i < n; i++)
{
setbitcount = countBits(arr[i]);
count[setbitcount].add(arr[i]);
}
// Used as an index in
// final sorted array
int j = 0;
// Traverse through all bit
// counts (Note that we sort
// array in decreasing order)
for (int i = 31; i >= 0; i--)
{
Vector<Integer> v1 = count[i];
for (int p = 0; p < v1.size(); p++)
arr[j++] = v1.get(p);
}
}
// Utility function to print
// an array
static void printArr(int arr[],
int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = arr.length;
sortBySetBitCount(arr, n);
printArr(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to sort an array according to # count of set bits using std::sort() # a utility function that returns total set bits # count in an integer def countBits(a): count = 0 while (a): if (a & 1 ): count += 1 a = a>>1 return count # Function to sort according to bit count # This function assumes that there are 32 # bits in an integer. def sortBySetBitCount(arr,n): count = [[] for i in range(32)] setbitcount = 0 for i in range(n): setbitcount = countBits(arr[i]) count[setbitcount].append(arr[i]) j = 0 # Used as an index in final sorted array # Traverse through all bit counts (Note that we # sort array in decreasing order) for i in range(31, -1, -1): v1 = count[i] for i in range(len(v1)): arr[j] = v1[i] j += 1 # Utility function to print an array def printArr(arr, n): print(*arr) # Driver Code arr = [1, 2, 3, 4, 5, 6] n = len(arr) sortBySetBitCount(arr, n) printArr(arr, n) # This code is contributed by mohit kumar 29
C#
// C# program to sort an
// array according to count
// of set bits using std::sort()
using System;
using System.Collections.Generic;
class GFG{
// a utility function that
// returns total set bits
// count in an integer
static int countBits(int a)
{
int count = 0;
while (a > 0)
{
if ((a & 1) > 0 )
count += 1;
a = a >> 1;
}
return count;
}
// Function to sort according to
// bit count. This function assumes
// that there are 32 bits in an integer.
static void sortBySetBitCount(int []arr,
int n)
{
List<int> []count =
new List<int>[32];
for (int i = 0;
i < count.Length; i++)
count[i] = new List<int>();
int setbitcount = 0;
for (int i = 0; i < n; i++)
{
setbitcount = countBits(arr[i]);
count[setbitcount].Add(arr[i]);
}
// Used as an index in
// readonly sorted array
int j = 0;
// Traverse through all bit
// counts (Note that we sort
// array in decreasing order)
for (int i = 31; i >= 0; i--)
{
List<int> v1 = count[i];
for (int p = 0; p < v1.Count; p++)
arr[j++] = v1[p];
}
}
// Utility function to print
// an array
static void printArr(int []arr,
int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6};
int n = arr.Length;
sortBySetBitCount(arr, n);
printArr(arr, n);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to sort an
// array according to count
// of set bits using std::sort()
// a utility function that
// returns total set bits
// count in an integer
function countBits(a)
{
let count = 0;
while (a > 0)
{
if ((a & 1) > 0 )
count += 1;
a = a >> 1;
}
return count;
}
// Function to sort according to
// bit count. This function assumes
// that there are 32 bits in an integer.
function sortBySetBitCount(arr,n)
{
let count = new Array(32);
for (let i = 0;
i < count.length; i++)
count[i] = [];
let setbitcount = 0;
for (let i = 0; i < n; i++)
{
setbitcount = countBits(arr[i]);
count[setbitcount].push(arr[i]);
}
// Used as an index in
// final sorted array
let j = 0;
// Traverse through all bit
// counts (Note that we sort
// array in decreasing order)
for (let i = 31; i >= 0; i--)
{
let v1 = count[i];
for (let p = 0; p < v1.length; p++)
arr[j++] = v1[p];
}
}
// Utility function to print
// an array
function printArr(arr,n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr = [1, 2, 3, 4, 5, 6];
let n = arr.length;
sortBySetBitCount(arr, n);
printArr(arr, n);
// This code is contributed by patel2127
</script>
Producción
3 5 6 1 2 4
Método 4: Usando MultiMap
Pasos:
- Cree un MultiMap cuyos valores clave serán el negativo del número de bits establecidos del elemento.
- Recorra la array y haga lo siguiente para cada elemento:
- Cuente el número de bits de conjunto de este elemento. Que sea ‘setBitCount’
- cuenta.insertar({(-1) * setBitCount, elemento})
- Recorra ‘contar’ e imprima los segundos elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// simple approach to sort
// an array according to
// count of set bits.
#include<bits/stdc++.h>
using namespace std;
// Function to count setbits
int setBitCount(int num){
int count = 0;
while ( num )
{
if ( num & 1)
count++;
num >>= 1;
}
return count;
}
// Function to sort By SetBitCount
void sortBySetBitCount(int arr[], int n)
{
multimap< int, int > count;
// Iterate over all values and
// insert into multimap
for( int i = 0 ; i < n ; ++i )
{
count.insert({(-1) *
setBitCount(arr[i]), arr[i]});
}
for(auto i : count)
cout << i.second << " " ;
cout << "\n" ;
}
// Driver Code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
sortBySetBitCount(arr, n);
}
// This code is contributed by Ashok Karwa
Java
// Java program to implement
// simple approach to sort
// an array according to
// count of set bits.
import java.io.*;
import java.util.*;
class GFG
{
// Function to count setbits
static int setBitCount(int num)
{
int count = 0;
while ( num != 0 )
{
if ( (num & 1) != 0)
count++;
num >>= 1;
}
return count;
}
// Function to sort By SetBitCount
static void sortBySetBitCount(int[] arr, int n)
{
ArrayList<ArrayList<Integer>> count = new ArrayList<ArrayList<Integer>>();
// Iterate over all values and
// insert into multimap
for( int i = 0 ; i < n ; ++i )
{
count.add(new ArrayList<Integer>(Arrays.asList((-1) * setBitCount(arr[i]), arr[i])));
}
Collections.sort(count, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
return o1.get(0).compareTo(o2.get(0));
}
});
for(int i = 0; i < count.size(); i++)
{
System.out.print(count.get(i).get(1) + " ");
}
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = arr.length;
sortBySetBitCount(arr, n);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to implement # simple approach to sort # an array according to # count of set bits. # Function to count setbits def setBitCount(num): count = 0 while (num): if (num & 1): count += 1 num = num >> 1 return count # Function to sort By SetBitCount def sortBySetBitCount(arr, n): count = [] # Iterate over all values and # insert into multimap for i in range(n): count.append([(-1) * setBitCount(arr[i]), arr[i]]) count.sort(key = lambda x:x[0]) for i in range(len(count)): print(count[i][1], end = " ") # Driver Code arr = [ 1, 2, 3, 4, 5, 6 ] n = len(arr) sortBySetBitCount(arr, n) # This code is contributed by rag2127
C#
// C# program to implement
// simple approach to sort
// an array according to
// count of set bits.
using System;
using System.Collections.Generic;
class GFG {
// Function to count setbits
static int setBitCount(int num){
int count = 0;
while ( num != 0)
{
if ( (num & 1) != 0)
count++;
num >>= 1;
}
return count;
}
// Function to sort By SetBitCount
static void sortBySetBitCount(int[] arr, int n)
{
List<Tuple<int, int>> count = new List<Tuple<int, int>>();
// Iterate over all values and
// insert into multimap
for( int i = 0 ; i < n ; ++i )
{
count.Add(new Tuple<int,int>((-1) * setBitCount(arr[i]), arr[i]));
}
count.Sort();
foreach(Tuple<int, int> i in count)
{
Console.Write(i.Item2 + " ");
}
Console.WriteLine();
}
static void Main() {
int[] arr = {1, 2, 3, 4, 5, 6};
int n = arr.Length;
sortBySetBitCount(arr, n);
}
}
Javascript
<script>
// Javascript program to implement
// simple approach to sort
// an array according to
// count of set bits.
// Function to count setbits
function setBitCount(num) {
count = 0
while (num) {
if (num & 1) {
count += 1
}
num = num >> 1
}
return count
}
// Function to sort By SetBitCount
function sortBySetBitCount(arr, n) {
let count = []
// Iterate over all values and
// insert into multimap
for (let i = 0; i < n; i++) {
count.push([(-1) * setBitCount(arr[i]), arr[i]])
}
count.sort((a, b) => a[0] - b[0])
for (let i = 0; i < count.length; i++)
document.write(count[i][1] + " ")
}
// Driver Code
let arr = [1, 2, 3, 4, 5, 6]
let n = arr.length
sortBySetBitCount(arr, n)
// This code is contributed by gfgking
</script>
Producción
3 5 6 1 2 4
Complejidad temporal: O(n log n)
Espacio auxiliar: O(n)
Este artículo es aportado por Nikhil Chakravartula y modificado por Ashok Karwa . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA