给定 n 个数，每次可以删除任意两个不同的数字，问最后能否删除完毕？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1905 天前的主题，其中的信息可能已经有所发展或是发生改变。

这题有什么特殊的地方吗？奇数个数字删不完，偶数个数字的话，如果有个数字的数量超过了 n/2，也删不完。面试官说存在数字数量小于 n/2 的也删不完的反例，没想出来。

数字

删除

奇数

个数

26 条回复 • 2019-08-30 17:37:17 +08:00

lxy42

2019-08-29 11:27:56 +08:00 via Android

也没规定只能有一个数字是重复的啊。如果多个数字重复呢？像 1 1 2 2 3 3 不就删不万。

lxy42

2019-08-29 11:28:23 +08:00 via Android

@lxy42 删不完

ipwx

2019-08-29 11:29:55 +08:00 via Android

@lxy42 删除两个自己选择的任意数字吧…… 删的完

Caballarii

2019-08-29 11:32:33 +08:00

@lxy42 12，23，31，删完了

zhucegeqiu

2019-08-29 11:48:59 +08:00 via iPhone

不存在反例
假设有重复数字小于 n/2 删不完的情况，不妨设最后剩下 2k 个 1，因为 1 的个数小于 n/2，那之前两两删除的数字对中，至少有 k 对两个都不是 1 的，那么换一下就可以删完了

lxy42

2019-08-29 13:39:01 +08:00 via Android

@ipwx @Caballarii 是我没想清楚。如果所有数字的重复次数小于等于 n/2，应该是可以删完的。

xml123

2019-08-29 14:00:54 +08:00

每次挑剩下数量最多的两个数就行了

xenme

2019-08-29 14:28:28 +08:00

觉得不存在反例。
假设剩下的数字为 A，那么剩下的就是 N(n>1) 对 A。
所有的已删除数字对必然包含 A，如果不包含 A，比如 BC，那么一定可以拆分成 AB/AC 删除。
由此可以确定，剩下数字 A 的个数必然大于 N/2

Archangell

2019-08-29 17:19:47 +08:00

全都相同的数怎么删的完例四个一

xenme

2019-08-29 17:22:20 +08:00 via iPhone

@Archangell 但这个不是反例

Archangell

2019-08-29 17:24:14 +08:00

@xenme 这不是反例是什么

2019-08-29 17:27:08 +08:00

题目不严谨，无法回答。
N 个数是否允许重复？
可以删除两个不同的数中的“可以”，是必须每次都删除两个不同的数，还是“可以”删相同的也可以删不同的，甚至也“可以”不删？

细节不严谨，限制不一样，答案就会不一样。

xenme

2019-08-29 17:28:37 +08:00 via iPhone

@Archangell 1 的重复次数 4 大于了 n/2 （也就是 4/2 ）

jjianwen68

2019-08-29 17:30:21 +08:00

数学问题有请数学专业的高手解答

xenme

2019-08-29 17:30:26 +08:00 via iPhone

@GM 肯定允许重复，否则就不存在题目了啊，偶数个不重复的肯定全删光啊。

可以的定义肯定也是只能是不同的两个数才可以删除，否则偶数个数字肯定也是全删光

daozhihun

2019-08-29 17:30:28 +08:00

感觉答主的回答没毛病，一个数字出现的次数没有超过 n/2 一定可以删完。你当时应该反问面试官，要他给你据一个例子

zealot0630

2019-08-29 17:47:06 +08:00 via Android

每次删除俩最多的，数学归纳法可证明可行

popvlovs

2019-08-29 17:55:08 +08:00

只要理解没有偏差，不存在反例，至少有 N/2 个一样的数

starsriver

2019-08-29 19:53:38 +08:00 via Android

能删光。

递增数列问题，数字就是符号，每次产生 n 个相同的数组合到数列后面，然后随机删去 2m 个数字。

不能最多减最少或最多减最多，你不能保证每次都有这种条件，应该是最多的减数量处于中间的，每次都进行计算，找到最多的和数量处于中间的，必然可以减完。

no1xsyzy

2019-08-30 09:39:45 +08:00

构造性证明啊
https://gist.github.com/no1xsyzy/8b6722db07b769494f52568c0a9d8154

no1xsyzy

2019-08-30 09:51:49 +08:00

直接排序后对切，然后 x[i] x[i+n/2] 各取一个，肯定能取空
排序后 x[i] != x[i+n/2]

kx5d62Jn1J9MjoXP

2019-08-30 10:58:46 +08:00

可以证明只要重复最多的数字不超过一半就能删完

catcalse

2019-08-30 10:58:50 +08:00

1。2。2.。2.2.3

rocketman13

2019-08-30 11:13:31 +08:00

不存在反例吧

luozic

2019-08-30 13:04:04 +08:00

构建对等数据集合 {{x },{y}} ，这个可以用有理数的集合论来分析了，咋删不完的？除非你这个“任意”是设计的。设计好的删除方式

codechaser

2019-08-30 17:37:17 +08:00 via Android

@GM 允许重复，必须每次删除两个不同的。