字符串权重均衡算法问题：寻找最优无效字符串及代码修复

你的当前代码逻辑存在根本性偏差：它直接选择权重最小的字符串作为无效字符串，但这只是在样例中碰巧符合结果，实际问题的核心是计算排除每个字符串后，让剩余字符串权重相等的最小操作次数，再从中选出操作次数最少的那个无效字符串——这和单个字符串的权重大小没有直接关联。

正确思路拆解 #

1. 计算字符串权重：这部分你的代码是正确的，通过字符映射求和得到每个字符串的权重。
2. 确定最优目标值：当需要将一组数调整为相同值且操作次数（绝对差之和）最小时，中位数是最优的目标值（平均数仅能最小化平方差，而非绝对差）。
3. 计算每个候选的操作次数：对每个字符串，假设它是无效的，取出剩余的权重列表，找到其中位数，然后计算所有权重到中位数的绝对差之和，这个和就是排除该字符串后的最小操作次数。
4. 筛选最优结果：比较所有候选的操作次数，选择操作次数最小的那个对应的字符串作为答案。

修正后的Ruby代码 #

# 构建字符到权重的映射，只需初始化一次
char_weights = {}
('a'..'z').each_with_index { |char, idx| char_weights[char] = idx + 1 }

t = gets.to_i
t.times do
  n = gets.to_i
  str_weights = []
  n.times do
    str = gets.chomp
    weight = str.chars.sum { |c| char_weights[c] }
    str_weights << [str, weight]
  end

  min_ops = Float::INFINITY
  invalid_str = ""

  # 遍历每个字符串，假设它是无效的，计算对应的操作次数
  str_weights.each_with_index do |(current_str, current_weight), idx|
    # 排除当前字符串，得到剩余的权重列表
    remaining_weights = str_weights.reject.with_index { |_, i| i == idx }.map { |_, w| w }
    # 排序后取中位数
    sorted_weights = remaining_weights.sort
    median = sorted_weights[sorted_weights.size / 2]
    # 计算总操作次数：所有剩余权重到中位数的绝对差之和
    total_ops = remaining_weights.sum { |w| (w - median).abs }
    # 更新最小操作次数及对应字符串
    if total_ops < min_ops
      min_ops = total_ops
      invalid_str = current_str
    end
  end

  puts invalid_str
end

代码关键部分解释 #

• 字符权重映射：提前初始化一次即可，避免重复构建，提升运行效率。
• 剩余权重处理：通过reject.with_index精准排除当前候选的字符串权重，确保剩余列表正确。
• 中位数计算：排序后取中间位置元素，无论剩余数量是奇数还是偶数，这个选择都能保证绝对差之和最小。
• 操作次数计算：通过绝对差求和，准确统计将所有剩余字符串调整到中位数权重所需的总操作次数。
• 最优结果筛选：全程跟踪最小操作次数及其对应的字符串，最终输出符合要求的无效字符串。

内容的提问来源于stack exchange，提问作者Aniket Tiwari