Readme

3644.Maximum-K-to-Sort-a-Permutation

这道题的第一反应是一定会有解吗？事实上本题的关键在于nums的值是0到n-1的排列。如果我们想到，0与任何数字的位与都是0，因此我们可以通过0与任意数字的交换来实现数组的重排序。举个例子，如果当前0是在index=4上，我们就寻找数组里的5并假设其在index=p的位置。通过(4,p)的交换，我们就把5送到了它应该去的位置（即idx=4），而把0送到了另一个p的位置。由此重复类似的操作。故k=0必然是一个解。

既然一定有解，那么最优解是什么呢？我们只需要考虑那些不在期望位置、必须重排的元素，记作v1,v2,...,vt。答案就是令k为这些元素的bitwise AND的结果。为什么这么神奇呢？首先k一定比这些v都要小，故k一定是落在[0,n-1]之间的。其次，我们发现v1&k, v2&k, ..., vt&k的结果一定都是k。所以我们只需要寻找nums的k所在的那个元素，把它类比于上述的0，就可以实现nums里对v1,v2,..,vt的任意重排。

有没有比k更好的答案了呢？不会，如果我们的交换涉及到比上述vi更多的元素，那么得到的bitwise AND的结果一定更小，结果也就一定比k更差。