JavaScript中生成指定切换次数的1/2向量高效实现咨询

原方法效率低的核心原因是随机重排的试错概率极低，尤其是当目标切换次数偏离随机分布均值时，会陷入大量无效循环。直接构造符合要求的序列才是最优解，步骤如下：

核心逻辑 #

切换次数k等价于向量中连续相同元素的块数为k+1（比如3次切换对应4个块：111|22|1|222）。我们只需构造出恰好k+1个块的序列即可。

前提验证 #

首先确认目标切换次数k是否合法：

• 若向量全为1或全为2，仅能实现0次切换；
• 否则，最小切换次数为1（如全1后接全2），最大切换次数为2*min(count1, count2)（交替排列直到其中一种元素耗尽）；
• 若k不在[1, 2*min(count1, count2)]范围内，直接返回无效提示。

具体实现步骤（以Python为例） #

1. 统计元素数量：先算出原向量中1的数量count1，2的数量count2，总长度n = count1 + count2。
2. 确定块的起始类型与分配：
   目标块数m = k + 1，分两种起始情况：
   • 以1开头：1的块数为t1 = (m + 1) // 2，2的块数为t2 = m // 2，需满足t1 <= count1且t2 <= count2；
   • 以2开头：2的块数为t2 = (m + 1) // 2，1的块数为t1 = m // 2，需满足t2 <= count2且t1 <= count1；
     选择满足条件的起始类型（若两种都满足，可随机选一种增加随机性）。
3. 分配每个块的元素个数：
   以1的块为例，将count1个1分配到t1个块中：
   • 基础个数：base = count1 // t1
   • 额外加1的块数：remain = count1 % t1
   • 得到1的块长度列表：blocks1 = [base+1]*remain + [base]*(t1-remain)
     同理生成2的块长度列表blocks2。
4. 拼接块序列：交替拼接1和2的块，按起始类型决定顺序，最后展开成向量。

代码示例 #

import random

def generate_target_switch_vector(count1, count2, target_k):
    n = count1 + count2
    min_count = min(count1, count2)
    max_possible_k = 2 * min_count
    # 验证合法性
    if count1 == 0 or count2 == 0:
        return [1]*count1 + [2]*count2 if target_k == 0 else None
    if not (1 <= target_k <= max_possible_k):
        return None
    
    m = target_k + 1
    # 确定起始类型
    start_with_1 = False
    t1_1 = (m + 1) // 2
    t2_1 = m // 2
    if t1_1 <= count1 and t2_1 <= count2:
        start_with_1 = random.choice([True, False]) if ((m//2) <= min(count1, count2)) else True
    elif (m + 1)//2 <= count2 and m//2 <= count1:
        start_with_1 = False
    else:
        return None  # 理论上不会走到这，因为前面验证过合法性
    
    # 生成块长度
    if start_with_1:
        t1, t2 = t1_1, t2_1
    else:
        t2, t1 = (m + 1) // 2, m // 2
    
    # 分配1的块
    base1, remain1 = divmod(count1, t1)
    blocks1 = [base1 + 1]*remain1 + [base1]*(t1 - remain1)
    random.shuffle(blocks1)  # 随机打乱块长度，增加序列随机性
    
    # 分配2的块
    base2, remain2 = divmod(count2, t2)
    blocks2 = [base2 + 1]*remain2 + [base2]*(t2 - remain2)
    random.shuffle(blocks2)
    
    # 拼接序列
    result = []
    if start_with_1:
        for b1, b2 in zip(blocks1, blocks2):
            result.extend([1]*b1)
            result.extend([2]*b2)
        # 如果块数是奇数，补上最后一个1的块
        if t1 > t2:
            result.extend([1]*blocks1[-1])
    else:
        for b2, b1 in zip(blocks2, blocks1):
            result.extend([2]*b2)
            result.extend([1]*b1)
        if t2 > t1:
            result.extend([2]*blocks2[-1])
    
    return result

# 示例：480个元素，假设1和2各240个，目标160次切换
count1 = 240
count2 = 240
target_k = 160
vector = generate_target_switch_vector(count1, count2, target_k)

# 验证切换次数
switch_count = 0
for i in range(1, len(vector)):
    if vector[i] != vector[i-1]:
        switch_count += 1
print(f"实际切换次数: {switch_count}")  # 输出应为160

优势说明 #

• 时间复杂度为O(n)，完全避免了随机试错的循环，处理480个元素的场景几乎瞬间完成；
• 可通过打乱块长度保证序列的随机性，和随机重排的结果分布一致；
• 直接确保生成的序列满足切换次数要求，无需后续验证。

内容的提问来源于stack exchange，提问作者0demo1