阅微客栈 » 头脑风暴

算法 - 均分数组

(6 posts)
  • 发起于 1 年 之前，作者 zhang
  • 最新回复 来自于 lemonutzf

Tags:

  1. zhang
    神

    给一个数组，将它们分为两部分，平均值相等。

    发布于 1 年 之前 #

  2. szuxjq
    Member

    不知道O(n)最快能达到多少

    发布于 1 年 之前 #

  3. szuxjq
    Member

    有人说是和子集问题差不多啊，复杂度有那么高？如果先排序了应该很快吧

    发布于 1 年 之前 #

  4. mathena
    Member

    看上去怎么像 NP?
    其实他们的平均值, 就是数组的平均值.

    发布于 1 年 之前 #

  5. szuxjq
    Member

    “平均值相等”和“分成两部分，其和相等”是否等价？

    发布于 1 年 之前 #

  6. lemonutzf
    Member

    其实就是子集和问题。
    mathena 说对了，他们的平均值, 就是数组的平均值.
    把数组中所有数都减去数组的平均值， 这样问题就变成 求一个子集其和为0的问题。

    发布于 7 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。