Game 280 problem2: minimum operands to turn an array into an alternating array

Title Description

The minimum number of operands to make an array an alternating array

Ideas

Minimal adjustment operation , It means that we put the odd （ accidentally ） The number of subscripts is adjusted to all odd （ accidentally ） The number that appears most often in a number of subscript digits , This will minimize the number of adjustments . At the same time, the numbers of odd and even subscripts should not be the same .
I thought of this idea during the competition , But in the process of doing it, I feel more and more troublesome , My thinking is becoming less and less clear , Less and less confident , As a result, it was not done . Hope to learn a lesson , Set up self-confidence in the process of doing questions 、 Theoretical confidence （ Cough …
The process ：

• Use two hash tables mp_0 and mp_1 Record the number of occurrences of each number on the odd and even positions respectively ;
• Sort the key value pairs in two hash tables by value , Get the number that appears the most times on the parity position . Here we need to put map The element in becomes pair<int, int>, Deposit in vector in , Handwriting cmp function , Give Way sort Function pair pair Value ordering for .
• The numbers that appear most frequently in the odd and even positions are respectively recorded as a1, b1, The number of occurrences is x1, y1; Those with the second highest number of occurrences are respectively recorded as a2, b2, The number of occurrences is x2, y2. Be careful ,a2 and b2 Not necessarily . Let's discuss in details ：
  • If a1 != b1： In the simplest case , Just change the original array to a1, b1, a1, b1,… Sequence , The number of modifications is n - x1 - y1 Time ,n Is array length , The same below ;
  • If a1 == b1, Then you need to find the answer in the number with the second most occurrences of odd and even subscripts . That is, we need to compare a1, b2 and a2, b1 Which of these two cases has the smallest operand . namely ans = min(n - x1 - y2, n - x2 - y1)
  • There's an extreme situation a2 and b2 It doesn't exist , So all the elements in the array are the same , At this time, you only need to change the number at the position of the odd subscript to any other number , The number of modifications is n / 2;

Code

class Solution {
public:
    static bool cmp(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }

    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        map<int, int> mp_0, mp_1;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                mp_0[nums[i]]++;
            } else {
                mp_1[nums[i]]++;
            }
        }
        vector<pair<int, int>> vec_0, vec_1;
        for (auto it = mp_0.begin(); it != mp_0.end(); it++) {
            vec_0.push_back(make_pair(it->first, it->second));
        }
        for (auto it = mp_1.begin(); it != mp_1.end(); it++) {
            vec_1.push_back(make_pair(it->first, it->second));
        }
        sort(vec_0.begin(), vec_0.end(), cmp);
        sort(vec_1.begin(), vec_1.end(), cmp);
        int x1 = vec_0[0].second, a1 = vec_0[0].first;
        int y1 = vec_1[0].second, b1 = vec_1[0].first;
        int x2 = -1, y2 = -1, a2 = -1, b2 = -1;
        if (vec_0.size() > 1) {
            x2 = vec_0[1].second;
            a2 = vec_0[1].first;
        }
        if (vec_1.size() > 1) {
            y2 = vec_1[1].second;
            b2 = vec_1[1].first;
        }
        int ans = INT_MAX;
        if (a1 != b1) {
            ans = min(ans, n - x1 - y1);
        } else {
            if (a2 == -1 && b2 == -1) {
                return n / 2;
            }
            if (a2 != -1) {
                ans = min(ans, n - x2 - y1);
            } 
            if (b2 != -1) {
                ans = min(ans, n - x1 - y2);
            } 
        }
        return ans;
    }
};

Improvement and summary

Use Lambda Expression writing cmp function ：

lambda Expression defines an anonymous function , And can capture a certain range of variables . The grammatical form is ：

[capture](params) opt -> ret {body;};

among captyre It's the capture list ,params It's a list of parameters ,opt It's a function option ,ret Is the return value type .

for example ：

auto func = [](int a) -> int {return a + 1;};

C++11 in ,lambda The return value type of an expression can be inferred automatically , Therefore, it can be omitted ->ret This part , It becomes ：

auto func = [](int a) {return a + 1;};

A common scenario is to declare in a function sort() The third argument to the function cmp() function .

typedef pair<int, int> PII;
int function() {
	auto cmp = [&](PII& a, PII& b) {
        return a.second > b.second;
    };
}

above lambda Expression ：

• [&] Indicates that external variables are captured by reference , You can also use [] Indicates that no variables are captured ,[=] Means to capture external variables by copying
• () The formal parameters of the function are written in , It is best to pass parameters by reference to avoid copying values .

You can also directly sort() The position of the third parameter of the function is written as lambda expression ：

sort(vec.begin(), vec.end(), [&](PII& a, PII& b) {
    return a.second > b.second;
});