标签：需要   使用   题解   owb   pre   ref   ace   最小   turn   

1674. 使数组互补的最少操作次数

? LeetCode第217周赛的第三题，比赛时卡了一个小时，没有想到O(n)的做法。对差分不熟悉，但是最关键的还是扫描的思路没有想到。由于这道题有这么几个点比较重要，觉得应该特别记录一下。

1. 扫描：比赛时我也想到了当选定和K处于个个区间[2, lo]、[lo, hi]、[sum, sum]时的状态。可是我把对于每个nums[i]的lo、hi、sum都看成独立的一套。没有联系起来。题解里面把所有数放在数轴上的思路是我第一次见到这种思想。
2. 差分：这题不一定一定要用差分，只是利用了差分的区间更新、单点查询的性质。实际上也可也用树状数组，或者更复杂的线段树（还没学过）。只是这里差分就可以完成。

//
// Created by root on 2020/11/30.
//
#include 

using namespace std;

class Solution {
public:
    // 差分数组：b[k]。
    // 差分数组更新，对[l, r]区间++：b[l]++, b[r + 1]--;
    // 和为k时最小操作次数即b[0] + b[1] + ... + b[k]
    vector b;
    void update(int l, int r, int x) {
        b[l] += x;
        b[r + 1] -= x;
    }
    int minMoves(vector& nums, int limit) {
        b.resize(limit * 2 + 2);

        int n = nums.size();
        for (int i = 0; i 

附上树状数组解法：

// 树状数组解法：区间更新、单点查询
class BIT {
public:
    vector trees;
    int max_n;
    BIT(int n) {
        trees.resize(n);
        max_n = n;
    }
    int lowBit(int x) {
        return x & (-x);
    }
    void update(int pos, int x) {
        for (int i = pos; i & nums, int limit) {
        BIT bit(limit * 2 + 2);
        int n = nums.size();
        for (int i = 0; i 

这道题让我对树状数组的使用理解又加深了一些，后面可能会总结一下树状数组的使用和前缀和、差分、树状数组这些简单的数据结构的区别和功能。

[LeetCode]1674. 使数组互补的最少操作次数（扫描 + 差分\树状数组）

标签：需要   使用   题解   owb   pre   ref   ace   最小   turn   

原文地址：https://www.cnblogs.com/enmac/p/14062417.html