Сартаванне цэлых лікаў па колькасці 1-бітнага рашэння Leetcode  


Узровень складанасці Лёгка
Часта пытаюцца ў Саман
алгарытмы Бітавая маніпуляцыя кадаваньне інтэрв'ю інтэрв'юп LeetCode LeetCodeSolutions сартаванне

Пастаноўка праблемы  

У задачы "Сартаванне цэлых лікаў па колькасці 1 біта" нам даецца масіў arr. Наша задача - адсартаваць элементы ў масіве паводле колькасці 1 біта ў двайковы прадстаўленне ліку ў парадку ўзрастання.

Калі два і больш лікаў у сваім двайковым прадстаўленні ўтрымліваюць аднолькавую колькасць 1 біт, у гэтым выпадку нам трэба адсартаваць іх у парадку павелічэння. arr [i] знаходзіцца паміж 0 і 10000.

Прыклад

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

Тлумачэнне:

Двайковае прадстаўленне кожнага ліку ў масіве:

Сартаванне цэлых лікаў па колькасці 1-бітнага рашэння LeetcodePin

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]. Для гэтага мы памножым лік 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]

Код Java для сартавання цэлых лікаў па колькасці 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  

Часовая складанасць

Часавая складанасць вышэйзгаданага кода Аб (п) таму што мы абыходзім дадзены масіў arr толькі адзін раз. Тут n - даўжыня дадзенага масіва arr.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Спасылкі