如何解决Coderbyte的Wave Sorting问题？正确性如何证明？

一、判断可行性的核心规则 #

要构造出a1 > a2 < a3 > a4 < ...的波浪数组，必须满足以下两个条件：

• 频率限制：数组中出现次数最多的元素的频次max_count不能超过(n + 1) // 2（n为数组长度）。如果超过，直接返回false——此时必然会出现至少两个该元素相邻在需要交替的位置，无法满足高低要求。
• 极值匹配（当max_count等于阈值时）：当max_count == (n + 1) // 2时，该高频元素必须是数组的最大值。只有这样，才能将其放在所有波峰位置（索引0、2、4...），每个波峰的最大值都能大于相邻波谷的其他元素，满足交替要求。

二、构造波浪数组的步骤 #

如果满足上述可行性条件，可按以下步骤构造符合要求的数组：

1. 排序数组：将数组升序排序。
2. 拆分并交叉排列：
   • 把排序后的数组分成前半部分（前n//2个元素）和后半部分（剩余元素）。
   • 从后半部分的第一个元素开始，依次取后半部分元素、前半部分元素，交替拼接成新数组。例如排序后的数组为[0,1,1,2,4,4]，后半部分是[2,4,4]，前半部分是[0,1,1]，拼接后得到[2,0,4,1,4,1]，正好符合波浪模式。
3. 验证（可选）：遍历拼接后的数组，检查是否满足arr[i] > arr[i+1]当i为偶数（从0开始），且arr[i] < arr[i+1]当i为奇数。这一步可确保构造的数组完全符合要求，避免特殊情况遗漏。

三、代码实现（Python） #

def WaveSorting(arr):
    n = len(arr)
    
    # 统计元素频率
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    max_count = max(freq.values())
    threshold = (n + 1) // 2
    
    if max_count > threshold:
        return "false"
    
    # 当max_count等于阈值时，检查是否为最大值
    if max_count == threshold:
        max_num = max(arr)
        high_freq_num = [k for k, v in freq.items() if v == max_count][0]
        if high_freq_num != max_num:
            return "false"
    
    # 构造波浪数组
    arr_sorted = sorted(arr)
    half = n // 2
    first_part = arr_sorted[:half]
    second_part = arr_sorted[half:]
    wave = []
    
    for i in range(half):
        wave.append(second_part[i])
        wave.append(first_part[i])
    if n % 2 == 1:
        wave.append(second_part[-1])
    
    # 验证波浪模式
    valid = True
    for i in range(n-1):
        if i % 2 == 0:
            if wave[i] <= wave[i+1]:
                valid = False
                break
        else:
            if wave[i] >= wave[i+1]:
                valid = False
                break
    return "true" if valid else "false"

四、正确性证明 #

1. 频率限制的必要性 #

假设存在元素x的出现次数max_count > (n+1)//2，根据鸽巢原理，无论如何排列，必然会出现至少两个x相邻在需要满足高低交替的位置（比如两个x出现在波峰和波谷的相邻位置），无法满足a_i > a_{i+1}或a_i < a_{i+1}的要求，因此必然无法构造波浪数组。

2. 极值匹配的必要性 #

当max_count == (n+1)//2时，高频元素需要占据所有波峰位置（共(n+1)//2个）。如果该元素不是最大值，波峰位置的元素会小于某些波谷位置的元素（排序后波谷元素来自前半部分，可能有比高频元素大的），导致a_i > a_{i+1}不成立。只有当高频元素是最大值时，每个波峰的最大值都能大于波谷的所有元素，确保交替条件成立。

3. 构造方法的正确性 #

排序后拆分并交叉排列，后半部分的元素整体大于等于前半部分（升序排序特性）。交替取后半和前半元素，使得波峰（后半元素）必然大于等于波谷（前半元素）。结合极值匹配条件，当高频元素是最大值时，波峰的最大值一定大于波谷元素，满足严格的交替要求。最后通过验证步骤排除特殊的相等情况，确保所有位置符合规则。

内容的提问来源于stack exchange，提问作者Jason Law