Ранжируйте массив в соответствии с крайним правым установленным битом и наименьшим установленным битом.
Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы заменить каждый элемент массива их рангом в соответствии с самым правым установленным битом (RSB) в порядке убывания. Если RSB одинаков для двух чисел, выберите тот, который имеет наименьшее количество установленных битов, если установленные биты двух чисел одинаковы, выберите число, которое идет первым в массиве.
Примеры:
Input: arr[] = {4, 5, 6, 7, 8}
Output: 2 4 3 5 1
Explanation: Then rank of elements is given by sorted descending of RSB.
Rank(8) = 1 as Rsb of 8(1000) is 8 and setbit count is 1.
Rank(4) = 2 as RSB of 4(0100) is 4 and setbit count is 1.
Rank(6) = 3 as RSB of 6(0110) is 2 and setbit count is 2.
Rank(5) = 4 as RSB of 5(0101) is 1 and setbit count is 2.
Rank(7) = 5 as Rsb of 7(0111) is 1 and setbit count is 3.
So, the answer will be { 2, 4, 3, 5, 1 }.Input: arr[] = {5, 10, 15, 32}
Output: 3 2 4 1
Наивный подход . Наивный подход состоит в том, чтобы найти ранг каждого элемента путем сравнения RSB этого элемента с другими элементами и увеличения ранга на 1 всякий раз, когда встречается большее значение RSB.
Сложность времени: О(Н*Н).
Вспомогательное пространство: НА).
Эффективный подход: чтобы оптимизировать описанный выше наивный подход, найдите ранги элементов, а затем присвойте ранг элементам с помощью компаратора. Используя компаратор, элементы можно сортировать на основе элементов данных. Например, здесь элементы будут отсортированы на основе RSB и количества установленных битов.
Ниже приведена реализация описанного выше подхода.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Class for pairclass 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 RSBbool 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
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;// Class for pairclass 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 RSBclass 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 logicclass 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] + " "); }} |
Временная сложность : O (N * log (N))
Вспомогательное пространство : O(N).