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 बिट की संख्या कम होती है वह पहले और छोटी संख्या पहले आती है।

हम इस समस्या को और भी आसान तरीके से हल कर सकते हैं। जैसा कि हम पहले से ही जानते हैं कि गिरफ्तारी [i] ० और १०००० के बीच की है। हम गिरफ्तारी [i] में एक बिट की संख्या और गिरफ्तारी का मूल्य दोनों ही स्टोर कर सकते हैं। इसके लिए, हम गिरफ्तारी [i] की १ बिट को १०००१ से गुणा करेंगे और गिरफ्तार [i] को जोड़ेंगे। यह मूल रूप से इस तरह दिखता है:

गिरफ्तार [i] = गिरफ्तार [i] + १०००१ * (गिरफ्त में १ बिट की संख्या [i]]

अब हम एरे को सॉर्ट करेंगे। जैसा कि हमें क्रमबद्ध सरणी को वापस करने की आवश्यकता है, इसलिए हम गिरफ्तारी [i]% 10001 को गिरफ्तारी [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 दी गई गिरफ्तारी सरणी की लंबाई है।

अंतरिक्ष की जटिलता

उपरोक्त कोड की अंतरिक्ष जटिलता है ओ (1) क्योंकि हम उत्तर को संग्रहीत करने के लिए केवल एक चर का उपयोग कर रहे हैं।

संदर्भ