1356. Sort Integers by The Number of 1 Bits

leetcode easy

#array#backtracking#bit-manipulation#csharp#easy#leetcode#sort#string

Task

Дан целочисленный массив 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.

C# solution

matched/original

using System;
using System.Linq;
public class Solution {
    public int[] SortByBits(int[] arr) {
        return arr.OrderBy(x => Convert.ToString(x, 2).Count(c => c == '1')).ThenBy(x => x).ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& SortByBits(vector<int>& arr) {
        return arr.OrderBy(x => Convert.ToString(x, 2).size()(c => c == '1')).ThenBy(x => x).ToArray();
    }
}

Java solution

matched/original

import java.util.Arrays;

public class Solution {
    public int[] sortByBits(int[] arr) {
        return Arrays.stream(arr)
            .boxed()
            .sorted((a, b) -> {
                int countA = Integer.bitCount(a);
                int countB = Integer.bitCount(b);
                return countA == countB ? a - b : countA - countB;
            })
            .mapToInt(i -> i)
            .toArray();
    }
}

JavaScript solution

matched/original

var sortByBits = function(arr) {
    return arr.sort((a, b) => {
        const countA = a.toString(2).split('1').length - 1;
        const countB = b.toString(2).split('1').length - 1;
        return countA === countB ? a - b : countA - countB;
    });
};

Go solution

matched/original

import (
    "sort"
    "strconv"
)

func sortByBits(arr []int) []int {
    sort.Slice(arr, func(i, j int) bool {
        countI := strconv.FormatInt(int64(arr[i]), 2)
        countJ := strconv.FormatInt(int64(arr[j]), 2)
        countOneI := 0
        countOneJ := 0
        
        for _, char := range countI {
            if char == '1' {
                countOneI++
            }
        }
        for _, char := range countJ {
            if char == '1' {
                countOneJ++
            }
        }
        if countOneI == countOneJ {
            return arr[i] < arr[j]
        }
        return countOneI < countOneJ
    })
    return arr
}

Explanation

Algorithm

Создание функции для подсчета единиц:

Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.

Сортировка массива:

Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

Возврат отсортированного массива:

Верните отсортированный массив.

😎