首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

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

  •  
  •   codechaser · 54 天前 · 2286 次点击
    这是一个创建于 54 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    26 回复  |  直到 2019-08-30 17:37:17 +08:00
        1
    lxy42   54 天前 via Android
    也没规定只能有一个数字是重复的啊。如果多个数字重复呢?像 1 1 2 2 3 3 不就删不万。
        2
    lxy42   54 天前 via Android
    @lxy42 删不完
        3
    ipwx   54 天前 via Android
    @lxy42 删除两个自己选择的任意数字吧…… 删的完
        4
    Caballarii   54 天前
    @lxy42 12,23,31,删完了
        5
    zhucegeqiu   54 天前 via iPhone
    不存在反例
    假设有重复数字小于 n/2 删不完的情况,不妨设最后剩下 2k 个 1,因为 1 的个数小于 n/2,那之前两两删除的数字对中,至少有 k 对两个都不是 1 的,那么换一下就可以删完了
        6
    lxy42   54 天前 via Android
    @ipwx @Caballarii 是我没想清楚。如果所有数字的重复次数小于等于 n/2,应该是可以删完的。
        7
    xml123   54 天前
    每次挑剩下数量最多的两个数就行了
        8
    xenme   54 天前
    觉得不存在反例。
    假设剩下的数字为 A,那么剩下的就是 N(n>1) 对 A。
    所有的已删除数字对必然包含 A,如果不包含 A,比如 BC,那么一定可以拆分成 AB/AC 删除。
    由此可以确定,剩下数字 A 的个数必然大于 N/2
        9
    Archangell   54 天前
    全都相同的数 怎么删的完 例 四个一
        10
    xenme   54 天前 via iPhone
    @Archangell 但这个不是反例
        11
    Archangell   54 天前
    @xenme 这不是反例 是什么
        12
    GM   54 天前
    题目不严谨,无法回答。
    N 个数是否允许重复?
    可以删除两个不同的数中的“可以”,是必须每次都删除两个不同的数,还是“可以”删相同的也可以删不同的,甚至也“可以”不删?

    细节不严谨,限制不一样,答案就会不一样。
        13
    xenme   54 天前 via iPhone
    @Archangell 1 的重复次数 4 大于了 n/2 (也就是 4/2 )
        14
    jjianwen68   54 天前
    数学问题有请数学专业的高手解答
        15
    xenme   54 天前 via iPhone
    @GM 肯定允许重复,否则就不存在题目了啊,偶数个不重复的肯定全删光啊。

    可以的定义肯定也是只能是不同的两个数才可以删除,否则偶数个数字肯定也是全删光
        16
    daozhihun   54 天前
    感觉答主的回答没毛病,一个数字出现的次数没有超过 n/2 一定可以删完。你当时应该反问面试官,要他给你据一个例子
        17
    zealot0630   54 天前 via Android
    每次删除俩最多的,数学归纳法可证明可行
        18
    popvlovs   54 天前
    只要理解没有偏差,不存在反例,至少有 N/2 个一样的数
        19
    starsriver   54 天前 via Android
    能删光。

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

    不能最多减最少或最多减最多,你不能保证每次都有这种条件,应该是最多的减数量处于中间的,每次都进行计算,找到最多的和数量处于中间的,必然可以减完。
        20
    no1xsyzy   53 天前
        21
    no1xsyzy   53 天前
    直接排序后对切,然后 x[i] x[i+n/2] 各取一个,肯定能取空
    排序后 x[i] != x[i+n/2]
        22
    ssynhtn   53 天前
    可以证明只要重复最多的数字不超过一半就能删完
        23
    catcalse   53 天前
    1。2。2.。2.2.3
        24
    rocketman13   53 天前
    不存在反例吧
        25
    luozic   53 天前
    构建对等数据集合 {{x },{y}} ,这个可以用有理数的集合论来分析了,咋删不完的? 除非你这个“任意”是设计的。 设计好的删除方式
        26
    codechaser   53 天前 via Android
    @GM 允许重复,必须每次删除两个不同的。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2451 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 00:32 · PVG 08:32 · LAX 17:32 · JFK 20:32
    ♥ Do have faith in what you're doing.