阅微客栈 » 头脑风暴

判断n个数是否为全排列

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

Tags:

  1. zhang
    神

    给一个n长的数组，判断它是否为一个1, 2, \cdots, n的全排列，要求在线形时间，常数空间内实现。

    发布于 1 年 之前 #

  2. szuxjq
    Member

    设5个变量，分别记录给数组的最小值，最大值，奇数的个数，偶数的个数，以及这n个数的和，顺序的扫描过去，如果最小值为1，最大值为n，和为n(n+1)/2，而且这n个数没有重复(根据n个数的和，奇数的个数，偶数的个数和n值得出结论)，则该数组为1,2, ... , n的一个全排列。

    发布于 1 年 之前 #

  3. xiexiexx
    Member

    szuxjq：
    1 2 3 4 5 6 7
    是全排列，按你的方法
    1 4 1 4 5 6 7
    按你的方法也是全排列，呵呵
    4个奇数，3个偶数，最大为7，最小为1，总和也对，呵呵。

    发布于 1 年 之前 #

  4. szuxjq
    Member

    xiexiexx: 你说的对，我原来只考虑到 1 3 3 3 4 这种情况，哎呀，惨了

    发布于 1 年 之前 #

  5. xiexiexx
    Member

    可以对每个a[i]进行操作：
    如果a[i]不在1,n范围内，则不对
    如果a[i] == i，则i++
    如果a[i] > i，则交换a[a[i]]和a[i]
    如果a[i] < i,则不对
    分摊复杂性是O(1),时间复杂度是O(n），还是in place algorithm

    发布于 1 年 之前 #

  6. szuxjq
    Member

    xiexiexx: 你的方法中，如果a[a[i]]等于a[i]呢？比如1 4 1 4 5 这样子

    发布于 1 年 之前 #

  7. xiexiexx
    Member

    对，中间应该加上如果a[i]>i，判断a[i]和a[a[i]]是否相等，如果不相等则交换，相等则不对。

    发布于 1 年 之前 #

  8. xiexiexx
    Member

    a[i]和a[a[i]]不等，意味着那个位置不是正确位置，可以调换。

    发布于 1 年 之前 #

  9. szuxjq
    Member

    “如果不相等则交换，相等则不对”。这样看来似乎没问题了，可是，只有这样一个方法吗？
    我还是对我的方法不死心哪。把n个数的和 拆成 奇数的和 以及 偶数的和。如果n为奇数，则 奇数的和=偶数的和+ (n+1)/2；如果n为偶数，则 偶数的和=奇数的和+ n/2。有了这个性质之后，好像能对付xiexiexx说的反例啊(1 3 3 3 5 和1 4 1 4 5 都不怕)。

    发布于 1 年 之前 #

  10. xiexiexx
    Member

    哈哈，你那个方法不行的。

    1 2 3 4 5 6 7
    1 2 1 4 7 6 7

    奇数的和也是对的，偶数的和也是对的。

    序列和相同，不意味着序列相同。

    不过，非常感谢你指出我的那个错误！！！ 我没检查出来，呵呵。死循环啊，恐怖的！

    发布于 1 年 之前 #

  11. szuxjq
    Member

    "序列和相同，不意味着序列相同", 嗯，看来是不行了。
    不客气，这种算法我没学过，孤陋寡闻，长见识了。

    发布于 1 年 之前 #

  12. zeaster
    Member

    xiexiexx的方法如果在a[i] > i这步调整了，需要从头开始再遍历一边吗？
    如果不需要，方法对数列2 3 5 4 2就不适用吧
    如果需要，时间复杂度就不是线性了吧

    发布于 1 年 之前 #

  13. vvizard
    Member

    step1:i=0,搜最值=（1+i & n-i）？ i++，yes=>step2 no=>exit i=x=>exit (这个x当然是根据n给出的，不必写了……)
    step2:砍掉最值，回到step1.

    发布于 11 月 之前 #

  14. vvizard
    Member

    或者

    把这N个数先排下序，然后（比较邻位是否相等&判断最大值是否为n） 即可。

    发布于 11 月 之前 #

  15. foo
    Member

    Algebraic decision tree模型下判断n个数当中是否有重复，下界是O(nlogn)的，而这个问题显然要更难...

    发布于 11 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。