1 बिट लेटकोड समाधानको संख्याले पूर्णांक क्रमबद्ध गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब
बिट हेरफेर क्रमबद्ध

समस्या बयान

समस्यामा "१ बिटको संख्याबाट पूर्णांक क्रमबद्ध गर्नुहोस्," हामीलाई एर्रे एर दिइन्छ। हाम्रो कार्य एरेमा एलिमेन्टहरू क्रमबद्ध गर्नु हो बिटमा १ बिटको संख्या अनुसार बाइनरी आरोही क्रम मा संख्या को प्रतिनिधित्व।

यदि दुई वा अधिक संख्याले तिनीहरूका बाइनरी प्रतिनिधित्वमा १ बिटको बराबर संख्या समावेश गर्दछ भने, त्यो अवस्थामा हामीले तिनीहरूलाई बढ्दो क्रममा क्रमबद्ध गर्न आवश्यक छ। एर [i] ० र १००००० बीचमा छ।

उदाहरणका

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

व्याख्या:

एर्रेमा प्रत्येक नम्बरको बाइनरी प्रतिनिधित्व:

1 बिट लेटकोड समाधानको संख्याले पूर्णांक क्रमबद्ध गर्नुहोस्

ले one एक बिट समावेश गर्दछ।

ले one एक बिट समावेश गर्दछ।

ले one एक बिट समावेश गर्दछ।

ले one एक बिट समावेश गर्दछ।

त्यसैले सर्त पछि शर्त अनुसार यो हुन्छ: [1,5,6,7]।

1 बिट लीटकोड समाधानको संख्या द्वारा क्रमबद्ध पूर्णाgers्गतको लागि दृष्टिकोण

यस समस्याको समाधानका लागि धेरै आधारभूत दृष्टिकोण एर्रेको प्रत्येक एलिमेन्टमा १ बिटको संख्या गणना गर्नु र एरे क्रमबद्ध गर्न कम्प्याटर फंक्शन प्रयोग गर्नु हो। तुलनाकर्ता प्रकार्य दुई तत्वहरू तुलना गर्दछ। यदि दुबै तत्वहरूमा १ बिटको फरक संख्या समावेश छ भने नम्बर १ जसमा १ बिटको थोरै संख्या हुन्छ पहिलो आउँछ अन्य सानो स smaller्ख्या पहिले आउँछ।

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

एर [i] = एर [i] + १०००१ * (अरिटमा १ बिटको संख्या [i])

अब हामी एर्रे सॉर्ट गर्नेछौं। जसरी हामीले क्रमबद्ध एर्रे फर्काउन आवश्यक छ त्यसैले हामी एर [i]% १०००१ एरमा भण्डार गर्नेछौं [i] र त्यसपछि एरे फिर्ता गर्नेछौं।

कार्यान्वयन

C ++ कोड बिटको संख्याको आधारमा क्रमबद्ध गर्नुहोस्

#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]

क्रमबद्ध अ Le्कको जटिलता विश्लेषण १ बिट लेटकोड समाधानको संख्याद्वारा

समय जटिलता

माथिको कोडको समय जटिलता हो ऊ) किनकि हामी दिईएको एर्रे एर्रेमा मात्र एक पटक ट्रेस गर्दैछौं। यहाँ n दिईएको एर्रेको लम्बाई हो।

ठाउँ जटिलता

माथिको कोडको स्पेस जटिलता हो O (१) किनभने हामी उत्तरहरू भण्डारण गर्नका लागि मात्र एउटा चल प्रयोग गरिरहेका छौं।

सन्दर्भ