Sort according to the number of 1 under digital binary

1356. Sort according to the number of 1 under digital binary - LeetCode (LeetCode CN. Com)

Rewrite the title sort.

Question (1): how to calculate the number of binary 1:

Method 1: Use / 2 or > > to shift, use & 1 to detect low 1, and set sum to count

Method 2: use n & (n-1) to remove the lowest 1, and the number of cycles is the number of 1

Question (2): how to rewrite the sort() STL function: that is, create a function character

It should be noted that the function needs to be decorated with static, otherwise it cannot be accessed.

Method 1: use Lambda expressions

[&] references access all scoped dynamic variables

[] access all scoped dynamic variables by value

[ted1, & ted2] access ted1 by value, access ted2 by reference

When the return type of the function cannot be recognized, add - > type at the end

class Solution {
public:
    static int countBit(int n){
        int ans = 0;
        while(n){
            n &= n-1;
            ans++;
        }
        return ans;
    }
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int x, int y)->bool{
            int a=countBit(x),b=countBit(y);
            return a==b? (x<y):(a<b);
        });
        return arr;
    }
};

Time O(nlogn), space O(n)

You can also use lambad to call lambad expressions:

Among them__ builtin_ The popcount() function calculates how many bits of a 32-bit unsigned integer are 1

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        auto proj = [](int x) {
            return pair{ __builtin_popcount(x), x };
        };
        sort(begin(arr), end(arr),
            [&](int a, int b) { return proj(a) < proj(b); });
        return arr;
    }
};

Method 2: function comparator

The function sort requires that this parameter cmp should be static. cmp calls countBit, so countBit also needs to be static;

Alternatively, you can write these two functions outside the class Solution. I found it on the Internet( https://www.cnblogs.com/BlueBlueSea/p/14030217.html):

Non static member (non-static) functions are dependent on specific objects, and middle note functions such as std::sort are global, so it is not possible to call non static member functions in sort. Static member functions or global functions are independent of specific objects and can be accessed independently without creating any object instances.

class Solution {
private:
    static int countBit(int n) {
        int ans = 0;
        while (n) {
            n &= n - 1;
            ans++;
        }
        return ans;
    }

    static bool cmp(int a, int b) {
        int m = countBit(a), n = countBit(b);
        if (m == n) {
            return a < b;
        }
        else {
            return m < n;
        }
    }

public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

Method 3: struct / class object comparator (function object comparator)

That is, use object overloading () in a class or structure to create an object comparator.

As follows:

struct cmp{
	bool operator()(const student &a, const student &b) {
		//(student& a,student& b) 
		if (a.id > b.id) {
			return false;
		}
		else {
			return true;
		}
	}
};
sort(vec.begin(),vec.end(),cmp());

Question (3): other skills

Due to the small amount of data, we can set an array with the size of arr.size() to save the number of 1 under the corresponding element binary.

You can directly use array comparison after internal for loop traversal. This avoids the need to repeatedly calculate the number of each element 1.

Problem (4): error analysis

Please analyze the problems in the following code:

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int x, int y)->bool{
            int a=0,b=0;
            while(x){
                if((x&1) == 1) a++;
                x>>=1;
            }
            while(y){
                if((y&1) == 1) b++;
                y>>=1;
            }
            return a==b? (x<y):(a<b);
        });
        return arr;
    }
};

When the test case is: [1024512256128,64,32,16,8,4,2,1], output the original case (not arranged in ascending order)

This is because x and y are modified during re shift. You can save x and y by setting variables.