Сложность: easy
Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.
Верните массив после сортировки.
Пример:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
👨💻 Алгоритм:
1⃣Создание функции для подсчета единиц:
Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.
2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.
3⃣Возврат отсортированного массива:
Верните отсортированный массив.
😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> sortByBits(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end(), [](int a, int b) {
int countA = __builtin_popcount(a);
int countB = __builtin_popcount(b);
return countA == countB ? a < b : countA < countB;
});
return arr;
}
};
Ставь 👍 и забирай 📚 Базу знаний