Clasifique la array de acuerdo con el bit establecido más a la derecha y los bits establecidos menos

Dada una array arr[] de N enteros, la tarea es reemplazar cada elemento de la array con su rango de acuerdo con el bit más a la derecha (RSB) de manera descendente. Si el RSB es el mismo para dos números, elija el que tiene el menor número de bits establecidos si los bits establecidos de dos números son iguales, luego elija el número que viene primero en la array.

Ejemplos:

Entrada: arr[] = {4, 5, 6, 7, 8}
Salida: 2 4 3 5 1
Explicación: Luego, el rango de los elementos se da por orden descendente de RSB.
Rango (8) = 1 como Rsb de 8 (1000) es 8 y el recuento de bits establecidos es 1.
Rango (4) = 2 como RSB de 4 (0100) es 4 y el recuento de bits establecidos es 1.
Rango (6) = 3 como RSB de 6(0110) es 2 y el número de bits fijados es 2.
Rango(5) = 4 ya que RSB de 5(0101) es 1 y el número de bits fijados es 2.
Rango(7) = 5 ya que Rsb de 7(0111) es 1 y setbit count es 3.
Entonces, la respuesta será { 2, 4, 3, 5, 1 }.

Entrada: arr[] = {5, 10, 15, 32}
Salida: 3 2 4 1

Enfoque ingenuo: el enfoque ingenuo es encontrar el rango de cada elemento comparando el RSB de ese elemento con otros elementos e incrementando el rango en 1 siempre que se encuentre un valor mayor de RSB.

Complejidad temporal: O(N*N).
Espacio Auxiliar: O(N).

Enfoque eficiente: para optimizar el enfoque ingenuo anterior, encuentre rangos de elementos y luego asigne el rango a los elementos usando un comparador . Usando un comparador, los elementos se pueden ordenar en función de los miembros de datos. Por ejemplo, aquí los elementos se ordenarán según el RSB y el número de bits establecidos.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Class for pair
class Pair {
    public:
    int index;
    int rsb;
    int setbit;
 
    // Constructor
    Pair(int index, int rsb, int setbit)
     :index(index),rsb(rsb),setbit(setbit)
    {
    }
};
 
// Comparator for sorting based on RSB
bool operator<(const Pair& a, const Pair& b)
    {
        if (a.rsb > b.rsb)
            return false;
        else if (a.rsb < b.rsb)
            return true;
        else if (a.setbit < b.setbit)
            return false;
        else if (b.setbit < a.setbit)
            return true;
        else if (a.index < b.index)
            return false;
        else
            return true;
    }
 
    // Function to rearrange the elements
    // according to Rightmpost set bits
    void rearrange(int ar[], int n)
    {
        // Creating priority queue from
        // sorting according to
        // rightmost set bit.
        priority_queue<Pair> pq;
 
        // For creating object of each element
        // so that it can be sorted
        for (int i = 0; i < n; i++) {
 
            // To calculate the rightmost
            // set bit in O(1)
            int k = (ar[i] & -ar[i]);
 
            // Creating a pair object
            // with rsb and index
            int setbit
                = __builtin_popcount(ar[i]);
 
            // Inserting the element
            // in priorityqueue
            pq.push(Pair(i, k, setbit));
        }
 
        int rank = 1;
        // Popping the element of queue
        // to get respective rank.
        while (!pq.empty()) {
            Pair p = pq.top();
            pq.pop();
            ar[p.index] = rank++;
        }
    }
 
    // Driver code
        int main()
    {
        int arr[] = { 4, 5, 6, 7, 8 };
        // To store the length of array
        int N = sizeof(arr) / sizeof(arr[0]);;
 
        // To call the rearrange function
        rearrange(arr, N);
        for (int i = 0; i < N; i++)
            cout<<arr[i]<<" ";
             
        return 0;
    }
 
// This code is contributed by Pushpesh raj.

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
// Class for pair
class Pair {
    int index;
    int rsb;
    int setbit;
 
    // Constructor
    Pair(int index, int rsb, int setbit)
    {
        this.index = index;
        this.rsb = rsb;
        this.setbit = setbit;
    }
}
 
// Comparator for sorting based on RSB
class pair_sort implements Comparator<Pair> {
    // Used for sorting in descending order
    // of rightmost set bit
    public int compare(Pair a, Pair b)
    {
        if (a.rsb > b.rsb)
            return -1;
        else if (a.rsb < b.rsb)
            return 1;
        else if (a.setbit < b.setbit)
            return -1;
        else if (b.setbit < a.setbit)
            return 1;
        else if (a.index < b.index)
            return -1;
        else
            return 1;
    }
}
 
// Class to implement the solution logic
class GFG {
 
    // Function to rearrange the elements
    // according to Rightmpost set bits
    void rearrange(int ar[], int n)
    {
        // Creating priority queue from
        // sorting according to
        // rightmost set bit.
        PriorityQueue<Pair> pq
            = new PriorityQueue<Pair>(new pair_sort());
 
        // For creating object of each element
        // so that it can be sorted
        for (int i = 0; i < n; i++) {
 
            // To calculate the rightmost
            // set bit in O(1)
            int k = (ar[i] & -ar[i]);
 
            // Creating a pair object
            // with rsb and index
            int setbit
                = Integer.bitCount(ar[i]);
            Pair p = new Pair(i, k, setbit);
 
            // Inserting the element
            // in priorityqueue
            pq.add(p);
        }
 
        int rank = 1;
        // Popping the element of queue
        // to get respective rank.
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
 
            ar[p.index] = rank++;
        }
    }
 
    // Driver code
    public static void main(String[] args)
        throws java.lang.Exception
    {
        int arr[] = { 4, 5, 6, 7, 8 };
 
        // Creating an object of class
        GFG ob = new GFG();
 
        // To store the length of array
        int N = arr.length;
 
        // To call the rearrange function
        ob.rearrange(arr, N);
        for (int i = 0; i < N; i++)
            System.out.print(arr[i] + " ");
    }
}

2 4 3 5 1 

Complejidad de tiempo : O(N*log(N))
Espacio auxiliar : O(N).