Tamamları 1 Bit Leetcode Həlli Sıralamasına görə sıralayın

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Tam ədədi 1 Bit sayına görə sırala” problemində bizə bir sıra arr verilmişdir. Bizim vəzifəmiz massivdəki elementləri içindəki 1 bit sayına görə sıralamaqdır binar sayın artan sırada göstərilməsi.

İki və ya daha çox ədədin ikili nümayəndəliyində bərabər sayda 1 bit varsa, bu halda onları artan sırada sıralamalıyıq. arr [i] 0 ilə 10000 arasındadır.

misal

arr=[7,1,6,5]

[1,5,6,7]

Explanation:

Dizidəki hər ədədin ikili təsviri:

Pin

7-də 3 bir bit var.

1-də 1 bir bit var.

6-də 6 bir bit var.

5-də 5 bir bit var.

beləliklə şərtə görə çeşidləndikdən sonra belə olur: [1,5,6,7].

1 Bit Leetcode Həlli Sıralamasına görə Tamsayıların Sıralanmasına Yanaşma

Bu problemi həll etmək üçün çox əsas yanaşma, massivin hər bir elementindəki 1 bit sayını saymaq və sonra sıra sıralamaq üçün bir müqayisə funksiyasından istifadə etməkdir. Müqayisələndirici funksiya iki elementi müqayisə edir. Hər iki elementdə fərqli 1 bit sayı varsa, onda az 1 bit olan rəqəm əvvəl gəlir, əksinə daha kiçik rəqəm gəlir.

Bu problemi daha ağıllı şəkildə də həll edə bilərik. Arr [i] -in 0 ilə 10000 arasında olduğunu bildiyimiz kimi. Arr [i] -də həm bir bitin sayını, həm də arr [i] dəyərini saxlaya bilərik. Bunun üçün arr [i] içindəki 1 bit sayını 10001 ilə vurub arr [i] əlavə edəcəyik. Bu, əsasən belə görünür:

arr [i] = arr [i] + 10001 * (arr [i] də 1 bit sayı)

İndi serialı sıralayacağıq. Sıralanmış massivi qaytarmalı olduğumuz üçün arr [i]% 10001-i arr [i] -də saxlayırıq və sonra massivi qaytararıq.

Həyata keçirilməsi

1 Bit Sayı ilə Tam Sıralayanlar üçün C ++ kodu

#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 Bit Sayı ilə Tam Sıralayanlar üçün Java kodu

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 Bit Leetcode Həlli Sırası ilə Sıralama Tamsayıların Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki verilən arr dizisindən yalnız bir dəfə keçirik. Burada n verilmiş sıra massivinin uzunluğudur.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References