فرز الأعداد الصحيحة بعدد 1 بت Leetcode الحل


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي
معالجة البت فرز

بيان المشكلة

في مشكلة "فرز الأعداد الصحيحة بعدد 1 بت" ، حصلنا على مصفوفة arr. مهمتنا هي فرز العناصر في المصفوفة وفقًا لعدد 1 بت في ملف ثنائي تمثيل الرقم بترتيب تصاعدي.

إذا احتوى رقمان أو أكثر على عدد متساوٍ من 1 بت في تمثيلهم الثنائي ، في هذه الحالة نحتاج إلى فرزهم بترتيب تصاعدي. تقع arr [i] بين 0 و 10000.

مثال

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

التفسير:

التمثيل الثنائي لكل رقم في المصفوفة:

فرز الأعداد الصحيحة بعدد 1 بت Leetcode الحل

7 يحتوي على 3 بت واحد.

1 يحتوي على 1 بت واحد.

6 يحتوي على 6 بت واحد.

5 يحتوي على 5 بت واحد.

لذلك بعد الفرز حسب الشرط يصبح: [1,5,6,7،XNUMX،XNUMX،XNUMX].

نهج لفرز الأعداد الصحيحة بعدد 1 بت Leetcode الحل

تتمثل الطريقة الأساسية لحل هذه المشكلة في حساب عدد 1 بت في كل عنصر من عناصر المصفوفة ثم استخدام دالة المقارنة لفرز المصفوفة. تقارن دالة المقارنة بين عنصرين. إذا كان كلا العنصرين يحتويان على عدد مختلف من 1 بت ، فإن الرقم الذي يحتوي على عدد أقل من 1 بت يأتي أولاً ، أما الرقم الأصغر فيأتي أولاً.

يمكننا حل هذه المشكلة بطريقة أكثر ذكاءً. كما نعلم بالفعل ، تقع arr [i] بين 0 و 10000. يمكننا تخزين كل من رقم بت واحد وقيمة arr [i] في arr [i] نفسها. لهذا ، سنضرب رقم 1 بت في arr [i] مع 10001 ونضيف arr [i]. يبدو هذا بشكل أساسي كما يلي:

arr [i] = arr [i] + 10001 * (عدد 1 بت في arr [i])

الآن سنقوم بفرز المصفوفة. نظرًا لأننا نحتاج إلى إرجاع المصفوفة التي تم فرزها ، فسنخزن arr [i]٪ 10001 في arr [i] ثم نعيد المصفوفة.

تطبيق

كود C ++ لفرز الأعداد الصحيحة بعدد 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 بت Leetcode الحل

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نجتاز مجموعة arr المحددة مرة واحدة فقط. هنا n هو طول مجموعة arr المحددة.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

المراجع