1 பிட் லீட்கோட் தீர்வின் எண்ணிக்கையால் முழு எண்ணுகளை வரிசைப்படுத்துங்கள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப்
பிட் கையாளுதல் வரிசையாக்க

சிக்கல் அறிக்கை

”1 பிட் எண்ணால் முழு எண்ணுகளை வரிசைப்படுத்து” என்ற சிக்கலில், எங்களுக்கு ஒரு வரிசை வழங்கப்படுகிறது. வரிசையில் உள்ள கூறுகளை 1 பிட் எண்ணுக்கு ஏற்ப வரிசைப்படுத்துவதே எங்கள் பணி பைனரி ஏறுவரிசையில் எண்ணின் பிரதிநிதித்துவம்.

இரண்டு அல்லது அதற்கு மேற்பட்ட எண்ணிக்கையானது அவற்றின் பைனரி பிரதிநிதித்துவத்தில் 1 பிட் சம எண்ணிக்கையைக் கொண்டிருந்தால், அந்த விஷயத்தில் நாம் அவற்றை அதிகரிக்கும் வரிசையில் வரிசைப்படுத்த வேண்டும். arr [i] 0 மற்றும் 10000 க்கு இடையில் உள்ளது.

உதாரணமாக

arr=[7,1,6,5]
[1,5,6,7]

விளக்கம்:

வரிசையில் உள்ள ஒவ்வொரு எண்ணின் பைனரி பிரதிநிதித்துவம்:

1 பிட் லீட்கோட் தீர்வின் எண்ணிக்கையால் முழு எண்ணுகளை வரிசைப்படுத்துங்கள்

7 இல் 3 ஒரு பிட் உள்ளது.

1 இல் 1 ஒரு பிட் உள்ளது.

6 இல் 6 ஒரு பிட் உள்ளது.

5 இல் 5 ஒரு பிட் உள்ளது.

எனவே நிபந்தனைக்கு ஏற்ப வரிசைப்படுத்திய பின் இது பின்வருமாறு: [1,5,6,7].

1 பிட் லீட்கோட் தீர்வின் எண்ணிக்கையால் வரிசை எண்களை அணுகலாம்

இந்த சிக்கலைத் தீர்ப்பதற்கான மிக அடிப்படையான அணுகுமுறை, வரிசையின் ஒவ்வொரு உறுப்புகளிலும் 1 பிட் எண்ணைக் கணக்கிடுவதோடு, வரிசையை வரிசைப்படுத்த ஒப்பீட்டு செயல்பாட்டைப் பயன்படுத்துவதும் ஆகும். ஒப்பீட்டாளர் செயல்பாடு இரண்டு கூறுகளை ஒப்பிடுகிறது. இரண்டு கூறுகளும் 1 பிட் வித்தியாசமான எண்ணிக்கையைக் கொண்டிருந்தால், 1 பிட் குறைவான எண்ணிக்கையைக் கொண்ட எண் முதலில் வரும், இல்லையெனில் சிறிய எண் முதலில் வருகிறது.

இந்த சிக்கலை ஒரு சிறந்த வழியில் கூட நாம் தீர்க்க முடியும். 0 மற்றும் 10000 க்கு இடையில் அர் [i] பொய் இருப்பதை நாம் ஏற்கனவே அறிந்திருக்கிறோம். ஒரு பிட்டின் எண்ணிக்கை மற்றும் அர் [i] இன் மதிப்பு இரண்டையும் அர் [i] இல் சேமிக்க முடியும். இதற்காக, 1 பிட் எண்ணை ar [i] இல் 10001 உடன் பெருக்கி arr [i] ஐ சேர்ப்போம். இது அடிப்படையில் இது போல் தெரிகிறது:

arr [i] = arr [i] + 10001 * (arr [i] இல் 1 பிட்டின் எண்ணிக்கை)

இப்போது நாம் வரிசையை வரிசைப்படுத்துவோம். வரிசைப்படுத்தப்பட்ட வரிசையை நாம் திருப்பித் தர வேண்டியிருப்பதால், arr [i]% 10001 ஐ arr [i] இல் சேமித்து பின்னர் வரிசையைத் திருப்புவோம்.

நடைமுறைப்படுத்தல்

1 பிட் எண்ணால் வரிசை எண்களுக்கு சி ++ குறியீடு

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> sortByBits(vector<int>& arr) {
        int n=arr.size();
        for(int i=0;i<n;i++)
        arr[i]+=10001*__builtin_popcount(arr[i]);
        sort(arr.begin(),arr.end());
        for(int i=0;i<n;i++)
        arr[i]=arr[i]%10001;
        return arr;
    }
int main() 
{ 
 vector<int> arr = {7,1,6,5}; 
  vector<int>ans=sortByBits(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[1,5,6,7]

1 பிட் எண்ணால் வரிசைப்படுத்துபவர்களுக்கான ஜாவா குறியீடு

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] sortByBits(int[] arr) {
        int n=arr.length;
        for(int i=0;i<n;i++)
        arr[i]+=10001*Integer.bitCount(arr[i]);
        Arrays.sort(arr);
        for(int i=0;i<n;i++)
        arr[i]=arr[i]%10001;
        return arr;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,6,5}; 
        int[]ans=sortByBits(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[1,5,6,7]

1 பிட் லீட்கோட் தீர்வின் எண்ணிக்கையால் வரிசை எண்களின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

மேலே உள்ள குறியீட்டின் நேர சிக்கலானது ஓ (n) ஏனென்றால், கொடுக்கப்பட்ட அர் வரிசையை ஒரு முறை மட்டுமே பயணிக்கிறோம். இங்கே n என்பது கொடுக்கப்பட்ட arr வரிசையின் நீளம்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (1) ஏனென்றால் பதிலைச் சேமிக்க ஒரு மாறி மட்டுமே பயன்படுத்துகிறோம்.

குறிப்புகள்