数组：找到使数组单峰性最小所需的最小交换次数？

Question

假设我们有一个整数数组。保证所有相邻的元素都不同。让我们使用以下关系式定义该数组a的双峰性为bt：

bt_array[i] = 0, if i == 0;
            = bt_array[i-1] + 1, if a[i] > a[i-1]
            = bt_array[i-1] - 1, if a[i] < a[i-1]
            = bt_array[i-1], if a[i] == a[i-1]

bt = last item in bt_array

当一个数组的比特位为0（如果它有奇数个元素），或者当它有偶数个元素时，它的比特位是+1或-1时，我们称其比特性为最小值。

问题是设计一种算法，找到使任何数组比特性最小所需的最少交换次数。这个算法的时间复杂度应该在最坏情况下是O(n)，n是数组中元素的数量。

例如，假设 a = {34,8,10,3,2,80,30,33,1}

它的初始bt为-2. 最小值为0。这可以通过只交换2和3来实现。因此输出应该是1。

以下是一些测试用例：

测试用例1：a = {34,8,10,3,2,80,30,33,1}，最小交换 = 1（交换2和3）

测试用例2：{1,2,3,4,5,6,7}：最小交换 = 2（将7和4交换以及将6和5进行交换）

测试用例3：{10,3,15,7,9,11}：最小交换 = 0。bt已经为1。

还有几个：

{2,5,7,9,5,7,1}：当前的bt = 2。交换5和7：minSwaps = 1

{1,7,8,9,10,13,11}：当前的bt = 4：交换1,8：minSwaps = 1

{13,12,11,10,9,8,7,6,5,4,3,2,1}：当前的bt = -12：交换（1,6），（2,5）和（3,4）：minSwaps = 3

---

我在面试中被问到这个问题，以下是我的回答：

1. Sort the given array.
2. Reverse the array from n/2 to n-1.
3. Compare from the original array how many elements changed their position. 
   Return half of it.

我的代码如下：

int returnMinSwaps(int[] a){
    int[] a = {1,2,3,4,5,6,7};
    int[] b = a;
    Arrays.sort(b);
    for(int i=0; i<= b.length/2 - 1; i++){
        swap(b[b.length - i], b[b.length/2 - i]);
    }
    int minSwaps = 0;
    for(int i=0;i<b.length;i++){
        if(a[i] != b[i])
            minSwaps++;
    }
    return minSwaps/2;
}

很不幸，使用这种逻辑我并没有得到一些测试案例所需的正确最小路径数量。同时，我正在排序该数组，这使得它的时间复杂度为O(n log n)，而实际上需要在O(n)的时间内完成。

- CodeHunter

---

@VidorVistrom：所有元素都是不同的。但我个人认为，你想问的是两个相邻元素是否是不同的吧？所有相邻元素都是不同的。我也会在编辑中加上这一点。感谢你指出了这个问题。 - CodeHunter

@YakymPirozhenko，交替排列只是双峰数组的一个特定情况。它可以是{+，-，+，-，...}或者也可以是{+，-，-，-，+，-，+，+}。这两种情况都有“最小双峰性”，如本问题所定义。 - darksky

@CodeHunter 哦，我明白了。所以整个数组不是唯一的。那么，如果交换导致相邻元素相同，如何计算结果数组的双峰性？您没有对a[i] == a[i - 1]时会发生什么情况进行条件判断。 - darksky

请注意，使用这个规则后，你不再需要保证初始数组中相邻的元素是不同的。现在它们可以是相同的，这会极大地改变问题的解决方式。 - darksky

@CodeHunter，你的一个例子是错误的！{1,7,8,9,10,13,11}：current bt = 4：Swap 1、7和8、9：minSwaps = 2实际上有minSwaps = 1，因为交换例如1和8（或者说7和9）会立即得到bt = 0。请等待，我已经制定并几乎证明了一组定理，说明目标交换次数是初始bt的函数，而与a无关。将尽快发布答案。 - hidefromkgb

Answer 1

紧急更新：T3不再保持！

考虑α = [0, 7, 8, 3, 4, 10, 1, 6, 9, 2, 5]。没有S_ij(α)可以使|B(α)|下降超过2。

思考对该方法的修改...

警告

此解决方案仅适用于没有相等数组元素的情况。

欢迎通过编辑答案提出概括性建议。

如果您想跳过无聊的部分，请直接转到结论。

介绍

让我们定义数组a上的交换操作符S_ij：

S_ij(a) : [… a_i, … a_j, …] → [… a_j, … a_i, …]   ∀i, j ∈ [0; |a|) ∩ ℤ : i ≠ j

让我们还将双峰性称为B(a)，并更正式地定义它：

显然的事实：

1. 交换是对称的：

   S_ij(a) = S_ji(a)

2. 如果两个交换的目标位置不相交，则它们是独立的：

   S_ij(S_kl(a)) = S_kl(S_ij(a))   ∀i, j, k, l : {i, j} ∩ {k, l} = ∅

3. 两个2-相关的交换互为反操作：

   S_ij(S_ij(a)) = a

4. 两个1-相关的交换遵循以下规则：

   S_jk(S_ij(a)) = S_ij(S_ik(a)) = S_ik(S_jk(a))

5. 等大小的数组的比特值差总是偶数：

   (B(a) – B(a')) mod 2 = 0   ∀a, a' : |a| = |a'|

   自然地，对于∀i : 0 < i < |a|,

   B([a_i–1, a_i]) – B([a'_i–1, a'_i]) = sgn(a_i – a_i–1) – sgn(a'_i – a'_i–1),

   它可以是 1 – 1 = 0，或 1 – –1 = 2，或 –1 – 1 = –2，或 –1 – –1 = 0，任何数量的±2和0相加都会得到偶数结果。

   注意：这仅在a中的所有元素彼此不同的情况下才成立，a'也是如此！

定理

[T1]   |B(S_ij(a)) – B(a)| ≤ 4   ∀a, S_ij(a)

不失一般性地，我们假设：

• 0 < i, j < |a| – 1
• j – i ≥ 2
• a_i–1 < a_i+1
• a_j–1 < a_j+1

如果满足条件a_i，则有以下三种情况：

1. a_i–1 < a_i < a_i+1: sgn(a_i – a_i–1) + sgn(a_i+1 – a_i) = 1 + 1 = 2
2. a_i < a_i–1 < a_i+1: sgn(a_i – a_i–1) + sgn(a_i+1 – a_i) = –1 + 1 = 0
3. a_i–1 < a_i+1 < a_i: sgn(a_i – a_i–1) + sgn(a_i+1 – a_i) = 1 + –1 = 0

当改变a_i并保留a的其他元素时，|B(a') – B(a)| ≤ 2（其中a'是产生的数组，上述三个条件也适用），因为除了来自与a_i相邻两个元素之外的其他B(a)项都没有更改其值。

S_ij(a)意味着如上所述两次发生，一次是针对a_i，一次是针对a_j。

因此，|B(S_ij(a)) – B(a)| ≤ 2 + 2 = 4.

类似地，对于每个角和j – i = 1，最大可能的增量为2，这是≤4。

最后，这直接推广到a_i–1 > a_i+1和a_j–1 > a_j+1。

证毕

[T2]   ∀a : |B(a)| ≥ 2   ∃S_ij(a) : |B(S_ij(a))| = |B(a)| – 2

{证明正在进行中，需要睡觉}

[T3]   ∀a : |B(a)| ≥ 4   ∃S_ij(a) : |B(S_ij(a))| = |B(a)| – 4

{证明正在进行中，需要睡觉}

结论

根据 T1、T2 和 T3，最小化 |B(a)| 所需的最小交换次数为：

⌊|B(a)| / 4⌋ + ß,

其中，如果 |B(a)| mod 4 ≥ 2，则 ß 等于 1，否则等于 0。

- hidefromkgb

---

非常感谢你的努力！+1。目前，我找不到任何反例，但我鼓励与此问题相关的人请验证一下。 另外，请问您能否解释一下T1的假设，特别是最后两个？当a[i-1]>a[i+1]和a[j-1]<a[j+1]时，也可能存在这种情况。我得出结论，在这种情况下，B(a)最终会被取消，T1仍然成立。请问您能否确认我的结论？ - CodeHunter

@CodeHunter 没错。有时候第一个位置是+2，第二个位置是-2（或者反过来），这样它们对最终的总和没有任何贡献。【更新：】附上证明... - hidefromkgb

@CodeHunter 但是我认为如果这是工业实践，你必须知道确切的交换方式。正如你提到的“交易数据分析模式”，难道你不想要一个可以告诉你确切交换方式的机制吗？ - Pushan Gupta

@CodeHunter 很抱歉我没有兑现今天证明的承诺，正在努力中。T2的主要思想是：为了达到至少B(a) = ±2，a必须具有至少3个连续递增或递减值的链（双峰性链±→±）。处理4个链（±→±→±）或更多的链很简单，因为我们可以取任意2个非边缘值并交换它们（±→∓→±），从而破坏链。所以，在T2中剩下要证明的是，∓→±→±→∓双峰性链（让我们称之为N链，因为如果用斜线绘制，它们类似于N-s）也能够被正确地破坏。 - hidefromkgb

@hidefromkgb：很酷。我已经在大多数测试用例上测试了你提供的逻辑，但没有失败。我认为这个想法是正确的！ - CodeHunter