Бүхэл тоог 1 битийн Leetcode шийдлийн тоогоор эрэмбэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe
Бит манипуляци Ангилах

Асуудлын мэдэгдэл

"Бүхэл тоонуудыг 1 битийн тоогоор эрэмбэлэх" гэсэн бодлогод бидэнд массив массив өгөгдсөн болно. Бидний даалгавар бол массив дахь элементүүдийг. Дахь 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].

1 битийн Leetcode шийдлийн тоогоор бүхэл тоонуудыг эрэмбэлэх арга

Энэ асуудлыг шийдвэрлэх хамгийн энгийн арга бол массивын элемент тус бүр дэх 1 битийн тоог тоолж дараа нь харьцуулах функцийг ашиглан массивыг эрэмбэлэх явдал юм. Харьцуулагч функц нь хоёр элементийг харьцуулдаг. Хэрэв хоёулаа өөр тооны 1 бит агуулсан бол 1 битээс цөөн тоог агуулсан тоо эхнийх байх болно.

Бид энэ асуудлыг илүү ухаалаг аргаар ч шийдэж чадна. Arr [i] нь 0-10000 хооронд байдгийг бид аль хэдийн мэдсэн тул arr [i] дотор нэг битийн тоо болон arr [i] -ийн утгыг хоёуланг нь хадгалах боломжтой. Үүний тулд arr [i] дэх 1 битийн тоог 10001-ээр үржүүлж arr [i] нэмнэ. Энэ нь үндсэндээ иймэрхүү харагдаж байна:

arr [i] = arr [i] + 10001 * (arr [i] дэх 1 битийн тоо)

Одоо бид массивыг ангилах болно. Бид эрэмбэлэгдсэн массивыг буцааж өгөх шаардлагатай байгаа тул arr [i]% 10001-ийг arr [i] -д хадгалаад массивыг буцааж өгөх болно.

Хэрэгжүүлэх

1 битийн тоогоор эрэмбэлэх бүхэл тоонд зориулсан 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 битийн тоогоор ангилах Java код

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 (N) Учир нь бид өгөгдсөн массивын массивыг ганц л удаа туулж байна. Энд n нь өгөгдсөн массив массивын урт юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (1) Учир нь бид хариултыг хадгалахын тулд зөвхөн хувьсагч ашиглаж байна.

Ашигласан материал