Readme

3785.Minimum-Swaps-to-Avoid-Forbidden-Values

首先考虑是否一定有解。我们比较容易想到，对于某个数值而言，如果forbidden里有x个禁放位置，但是nums有多于n-x个这样数值的元素。那么我们如何摆放，都必然会有元素落入禁放位置。反之，该数值的元素必然可以在非禁放位置妥善放置。

在排除掉无解的情况后，我们会想到最直观的贪心决策：我们只需要将两个处在违禁位置、且数值不同的元素交换，就可以一箭双雕，实现最高效的消除操作。这就类似于majority voting的模版题。具体的做法是：遍历每个位置，如果该位置不合规则（即nums[i]==forbidden[i]），我们就按数值统计频次。最终得到数组arr=[x1,x2,...,xi]表示每种数值有多少个违禁位置。每一次前述“一箭双雕”的swap，必然能同时解决两处的违禁问题，相当于在这个数组里找到一对pair都进行减1操作。

根据majority voting的原理，如果arr数组里没有超过半数的绝对多数元素，那么总可以将不同元素配对并消除。故总操作数是(total+1)/2. 其中total是arr的元素总和，+1是为了处理total为奇数的情况。另一种情况：如果存在绝对多数元素的频次mx大于total的半数，那么我们必须做满mx次swap才能将绝对多数的元素消除干净（其中前total-mx次可以与非绝对多数元素配对来实现非绝对多数元素的消除）。