arrays - 确定数组是否包含n ... n + m的算法？

Question

我在 Reddit 上看到了这个问题，并没有提出积极的解决方案，我认为在这里问这个问题是一个完美的问题。这是关于面试问题的线程：

编写一个方法，该方法接受一个大小为 m 的 int 数组，如果该数组由数字 n...n+m-1、该范围内的所有数字和该范围内的数字组成，则返回 (True/False)。不保证对数组进行排序。（例如，{2,3,4} 将返回 true。{1,3,1} 将返回 false，{1,2,4} 将返回 false。

我遇到的问题是我的面试官一直要求我进行优化（更快的 O(n)、更少的内存等），以至于他声称你可以使用恒定数量的数组在一次遍历中做到这一点记忆。从来没想过那个。

连同您的解决方案，请说明他们是否假定数组包含唯一项目。还要指出您的解决方案是否假定序列从 1 开始。（我稍微修改了问题以允许出现 2、3、4 的情况......）

编辑：我现在认为不存在处理重复的时间线性和空间常数算法。任何人都可以验证这一点吗？

重复问题归结为测试数组是否在 O(n) 时间、O(1) 空间中包含重复项。如果可以做到这一点，您可以先简单地测试，如果没有重复，则运行发布的算法。那么你能在 O(n) 时间 O(1) 空间中测试欺骗吗？

Answer 1

在不允许小于 1 的数字且没有重复的假设下，有一个简单的求和恒等式 - 从1到 以m为增量的数字1之和(m * (m + 1)) / 2。然后，您可以对数组求和并使用此标识。

上面的保证下可以查到有没有被骗，加上保证没有数字大于m或者小于n（可以打卡O(N)）

伪代码中的想法：
0) 从 N = 0 开始
1) 取列表中的第 N 个元素。
2）如果列表已排序，但它不在正确的位置，请检查它应该在哪里。
3）如果它应该在的地方已经有相同的数字，你有一个骗子 - 返回 TRUE
4）否则，交换数字（将第一个数字放在正确的位置）。
5) 用你刚刚交换的号码，它在正确的地方吗？
6）如果不是，返回第二步。
7) 否则，从第一步开始，N = N + 1。如果这超出了列表的末尾，那么你就没有欺骗了。

而且，是的，O(N)虽然它看起来像O(N ^ 2)

给大家的注意（从评论中收集的东西）

此解决方案在您可以修改数组的假设下工作，然后使用就地基数排序（实现O(N)速度）。

已经提出了其他数学解决方案，但我不确定它们中的任何一个是否已被证明。有一堆总和可能有用，但其中大多数会在表示总和所需的位数方面出现爆炸，这将违反恒定的额外空间保证。我也不知道他们中的任何一个是否能够为给定的一组数字产生一个不同的数字。我认为平方和可能有效，它有一个已知的计算公式（参见Wolfram's）

新见解（嗯，更多的沉思无助于解决它，但很有趣，我要睡觉了）：

因此，有人提到可能使用 sum + sum of squares。没有人知道这是否有效，我意识到它只有在 (x + y) = (n + m) 时才会成为问题，例如事实 2 + 2 = 1 + 3。正方形也有这个问题，这要归功于毕达哥拉斯三元组（所以 3^2 + 4^2 + 25^2 == 5^2 + 7^2 + 24^2，平方和不起作用）。如果我们使用费马大定理，我们知道这对于 n^3 是不会发生的。但是我们也不知道是否没有 x + y + z = n （除非我们知道但我不知道）。所以不能保证这也不会中断——如果我们继续沿着这条路走下去，我们很快就会用完比特。

然而，在我的喜悦中，我忘记指出你可以打破平方和，但这样做你会创建一个无效的正常和。我不认为你可以两者都做，但是，正如已经指出的那样，我们都没有任何证据。

---

我必须说，找到反例有时比证明事情容易得多！考虑以下序列，它们的总和为 28，平方和为 140：

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

我找不到长度为 6 或更短的任何此类示例。如果您也想要一个具有正确最小值和最大值的示例，请尝试长度为 8 的示例：

[1, 3, 3, 4, 4, 5, 8, 8]

---

更简单的方法（修改 hazzen 的想法）：

长度为 m 的整数数组包含从 n 到 n+m-1 的所有数字恰好一次当且仅当

• 每个数组元素都在 n 和 n+m-1 之间
• 没有重复

（原因：在给定的整数范围内只有 m 个值，所以如果数组在这个范围内包含 m 个唯一值，则它必须每个都包含一次）

如果您被允许修改数组，您可以使用 hazzen 算法思想的修改版本一次性检查列表（无需进行任何求和）：

• 对于从 0 到 m-1 的所有数组索引 i
  1. 如果 array[i] < n 或 array[i] >= n+m => RETURN FALSE（“发现值超出范围”）
  2. 计算 j = array[i] - n（这是从 n 到 n+m-1的排序数组中 array[i] 从 0 开始的位置）
  3. 虽然 j 不等于 i
     1. 如果 list[i] 等于 list[j] => RETURN FALSE ("duplicate found")
     2. 将 list[i] 与 list[j] 交换
     3. 重新计算 j = array[i] - n
• 返回真

我不确定原始数组的修改是否计入 O(1) 的最大允许额外空间，但如果不是，这应该是原始发布者想要的解决方案。

Answer 2

通过与您合作a[i] % a.length而不是您将问题减少到a[i]需要确定您已获得数字。0a.length - 1

我们认为这个观察是理所当然的，并尝试检查数组是否包含 [0,m)。

找到第一个不在正确位置的节点，例如

0 1 2 3 7 5 6 8 4 ;     the original dataset (after the renaming we discussed)
        ^
        `---this is position 4 and the 7 shouldn't be here

将该号码交换到应有的位置。即交换7与8：

0 1 2 3 8 5 6 7 4 ; 
        |     `--------- 7 is in the right place.
        `--------------- this is now the 'current' position

现在我们重复这一点。再看看我们当前的位置，我们问：

“这里的号码是正确的吗？”

• 如果不是，我们将其交换到正确的位置。
• 如果它在正确的位置，我们向右移动并再次执行此操作。

再次遵循这个规则，我们得到：

0 1 2 3 4 5 6 7 8 ;     4 and 8 were just swapped

这将逐渐正确地从左到右建立列表，每个数字最多移动一次，因此这是 O(n)。

如果有骗子，我们会在尝试交换backwards列表中的数字时立即注意到它。

Answer 3

为什么其他解决方案使用每个值的总和？我认为这是有风险的，因为当您将 O(n) 个项目加在一起成为一个数字时，从技术上讲，您使用的空间超过了 O(1) 个。

更简单的方法：

第1步，找出是否有任何重复。我不确定这在 O(1) 空间中是否可行。无论如何，如果有重复，则返回 false。

第 2 步，遍历列表，跟踪最低和最高项目。

第 3 步，（最高 - 最低）是否等于 m ？如果是，则返回 true。

Answer 4

任何一次性算法都需要 Omega(n) 位的存储空间。

相反，假设存在使用 o(n) 位的一次性算法。因为它只通过一次，它必须汇总 o(n) 空间中的前 n/2 个值。由于有 C(n,n/2) = 2^Theta(n) 从 S = {1,...,n} 中抽取的 n/2 个可能的集合，因此存在两个不同的集合 A 和 B 的 n/ 2个值，使得两者之后的内存状态相同。如果 A' = S \ A 是补充 A 的“正确”值集，则算法可能无法正确回答输入

A A' - 是的

B A' - 没有

因为它无法区分第一种情况和第二种情况。

量子点

Answer 5

这是 O(n) 中的工作解决方案

这是使用 Hazzen 建议的伪代码加上我自己的一些想法。它也适用于负数，不需要任何平方和的东西。

function testArray($nums, $n, $m) {
    // check the sum. PHP offers this array_sum() method, but it's
    // trivial to write your own. O(n) here.
    if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) {
        return false;    // checksum failed.
    }
    for ($i = 0; $i < $m; ++$i) {
        // check if the number is in the proper range
        if ($nums[$i] < $n || $nums[$i] >= $n + $m) {
            return false;  // value out of range.
        }

        while (($shouldBe = $nums[$i] - $n) != $i) {
            if ($nums[$shouldBe] == $nums[$i]) {
                return false;    // duplicate
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$shouldBe];
            $nums[$shouldBe] = $temp;
        }
    }
    return true;    // huzzah!
}

var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5));  // true
var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5));  // true
var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5));  // false - out of range
var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5));  // false - checksum fail
var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5));  // false - dupe
var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true

Answer 6

不久前，我从一个为电话公司工作的人那里听说了一个非常聪明的排序算法。他们必须对大量电话号码进行分类。在经历了一堆不同的排序策略之后，他们终于找到了一个非常优雅的解决方案：他们只是创建了一个位数组，并将位数组中的偏移量视为电话号码。然后，他们单次扫描他们的数据库，将每个数字的位更改为 1。之后，他们扫描了一次位数组，吐出电话号码以查找该位设置为高的条目。

按照这些思路，我相信您可以将数组本身中的数据用作元数据结构来查找重复项。最坏的情况，你可以有一个单独的数组，但我很确定如果你不介意交换一点，你可以使用输入数组。

我将暂时省略 n 参数，b/c 只会混淆事物 - 添加索引偏移量很容易做到。

考虑：

for i = 0 to m
  if (a[a[i]]==a[i]) return false; // we have a duplicate
  while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i)
  sum = sum + a[i]
next

if sum = (n+m-1)*m return true else return false

这不是 O(n) - 可能更接近 O(n Log n) - 但它确实提供了恒定空间，并且可能为问题提供不同的攻击向量。

如果我们想要 O(n)，那么使用字节数组和一些位操作将为重复检查提供额外的 n/32 字节内存使用（当然，假设是 32 位整数）。

编辑：上述算法可以通过将总和检查添加到循环内部来进一步改进，并检查：

if sum > (n+m-1)*m return false

这样它会很快失败。

Answer 7

如果我错了，请投票给我，但我认为我们可以确定是否存在重复或不使用方差。因为我们事先知道平均值（n + (m-1)/2 或类似的东西），所以我们可以将数字和差的平方相加来表示总和是否与方程匹配（mn + m(m-1 )/2)，方差为 (0 + 1 + 4 + ... + (m-1)^2)/m。如果方差不匹配，很可能我们有重复。

编辑：方差应该是 (0 + 1 + 4 + ... + [(m-1)/2]^2)*2/m，因为一半的元素小于平均值，另一半是大于平均值。

如果存在重复项，则上述方程中的一项将与正确序列不同，即使另一个重复项完全抵消了均值的变化。因此，仅当总和和方差都与我们可以预先计算的所需值匹配时，该函数才返回 true。

Answer 8

假设您只知道数组的长度并且您可以修改数组，它可以在 O(1) 空间和 O(n) 时间内完成。

该过程有两个简单的步骤。1.“模排序”数组。[5,3,2,4] => [4,5,2,3] (O(2n)) 2. 检查每个值的邻居是否比自身高一个（模）（O(n)）

总而言之，您最多需要 3 次通过数组。

模排序是“棘手”的部分，但目标很简单。获取数组中的每个值并将其存储在其自己的地址（模长度）。这需要遍历数组，循环遍历每个位置，通过将其交换到正确位置并在其目的地移动值来“驱逐”其值。如果您移动的值与您刚刚驱逐的值一致，则您有一个副本并且可以提前退出。最坏的情况是 O(2n)。

检查是一次通过数组检查每个值及其下一个最高邻居。总是 O(n)。

组合算法为 O(n)+O(2n) = O(3n) = O(n)

我的解决方案中的伪代码：

foreach(值[])
  而（值[i] 与 i 不一致）
    被驱逐=值[i]
    evict(values[i]) // 交换到它的“正确”位置
    if(values[i]%length == 被驱逐%length)
      返回假；// 当我们驱逐那个数字时，一个“重复”到达
  结束时
结束 foreach
foreach(值[])
  if((值[i]+1)%length != 值[i+1]%length)
    返回假
结束 foreach

我在下面包含了 Java 代码概念证明，它并不漂亮，但它通过了我为它所做的所有单元测试。我称它们为“StraightArray”，因为它们对应于顺子的扑克手（忽略花色的连续序列）。

public class StraightArray {    
    static int evict(int[] a, int i) {
        int t = a[i];
        a[i] = a[t%a.length];
        a[t%a.length] = t;
        return t;
    }
    static boolean isStraight(int[] values) {
        for(int i = 0; i < values.length; i++) {
            while(values[i]%values.length != i) {
                int evicted = evict(values, i);
                if(evicted%values.length == values[i]%values.length) {
                    return false;
                }
            }
        }
        for(int i = 0; i < values.length-1; i++) {
            int n = (values[i]%values.length)+1;
            int m = values[(i+1)]%values.length;
            if(n != m) {
                return false;
            }
        }
        return true;
    }
}

Answer 9

Hazzen 在 C 中的算法实现

#include<stdio.h>

#define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];

int check_ntom(int a[], int n, int m) {
    int i = 0, j = 0;
    for(i = 0; i < m; i++) {
        if(a[i] < n || a[i] >= n+m) return 0;   //invalid entry
        j = a[i] - n;
        while(j != i) {
            if(a[i]==a[j]) return -1;           //bucket already occupied. Dupe.
            swapxor(a, i, j);                   //faster bitwise swap
            j = a[i] - n;
            if(a[i]>=n+m) return 0;             //[NEW] invalid entry
        }
    }
    return 200;                                 //OK
}

int main() {
    int n=5, m=5;
    int a[] = {6, 5, 7, 9, 8};
    int r = check_ntom(a, n, m);
    printf("%d", r);
    return 0;
}

编辑：对代码进行更改以消除非法内存访问。

Answer 10

boolean determineContinuousArray(int *arr, int len)
{
    // Suppose the array is like below:
    //int arr[10] = {7,11,14,9,8,100,12,5,13,6};
    //int len = sizeof(arr)/sizeof(int);

    int n = arr[0];

    int *result = new int[len];
    for(int i=0; i< len; i++)
            result[i] = -1;
    for (int i=0; i < len; i++)
    {
            int cur = arr[i];
            int hold ;
            if ( arr[i] < n){
                    n = arr[i];
            }
            while(true){
                    if ( cur - n >= len){
                            cout << "array index out of range: meaning this is not a valid array" << endl;
                            return false;
                    }
                    else if ( result[cur - n] != cur){
                            hold = result[cur - n];
                            result[cur - n] = cur;
                            if (hold == -1) break;
                            cur = hold;

                    }else{
                            cout << "found duplicate number " << cur << endl;
                            return false;
                    }

            }
    }
    cout << "this is a valid array" << endl;
    for(int j=0 ; j< len; j++)
            cout << result[j] << "," ;
    cout << endl;
    return true;
}

Answer 11

ciphwn 是对的。这一切都与统计有关。从统计学的角度来看，问题是数字序列是否形成离散的均匀分布。离散均匀分布是指一组有限的可能值中的所有值均等概率。幸运的是，有一些有用的公式可以确定离散集是否一致。首先，确定集合 (a..b) 的平均值为 (a+b)/2，方差为 (nn-1)/12。接下来，确定给定集合的方差：

variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n

然后与预期方差进行比较。这将需要对数据进行两次传递，一次是确定平均值，一次是计算方差。

参考：

• 均匀离散分布
• 方差

Answer 12

哎呀！我陷入了一个重复的问题，在这里没有看到已经相同的解决方案。我以为我终于做了一些原创的事情！这是我稍微高兴一点的历史档案：

---

好吧，我不确定这个算法是否满足所有条件。事实上，我什至还没有验证它是否适用于我尝试过的几个测试用例。即使我的算法确实有问题，希望我的方法能激发一些解决方案。

据我所知，该算法在恒定内存中工作并扫描数组三次。也许一个额外的好处是它适用于整个整数范围，如果这不是原始问题的一部分的话。

我不是一个伪代码人，我真的认为代码可能比文字更有意义。这是我用 PHP 编写的一个实现。注意评论。

function is_permutation($ints) {

  /* Gather some meta-data. These scans can
     be done simultaneously */
  $lowest = min($ints);
  $length = count($ints);

  $max_index = $length - 1;

  $sort_run_count = 0;

  /* I do not have any proof that running this sort twice
     will always completely sort the array (of course only
     intentionally happening if the array is a permutation) */

  while ($sort_run_count < 2) {

    for ($i = 0; $i < $length; ++$i) {

      $dest_index = $ints[$i] - $lowest;

      if ($i == $dest_index) {
        continue;
      }

      if ($dest_index > $max_index) {
        return false;
      }

      if ($ints[$i] == $ints[$dest_index]) {
        return false;
      }

      $temp = $ints[$dest_index];
      $ints[$dest_index] = $ints[$i];
      $ints[$i] = $temp;

    }

    ++$sort_run_count;

  }

  return true;

}

Answer 13

任何连续数组 [ n, n+1, ..., n+m-1 ] 都可以使用模运算符映射到“基本”区间 [ 0, 1, ..., m ]。对于区间中的每个 i，基本区间中恰好有一个 i%m，反之亦然。

任何连续数组也有一个“跨度”m（最大值 - 最小值 + 1）等于它的大小。

使用这些事实，您可以创建一个大小相同的“遇到”布尔数组，最初包含所有错误，并在访问输入数组时，将其相关的“遇到”元素设置为真。

该算法在空间上为 O(n)，在时间上为 O(n)，并检查重复项。

def contiguous( values )
    #initialization
    encountered = Array.new( values.size, false )
    min, max = nil, nil
    visited = 0

    values.each do |v|

        index = v % encountered.size

        if( encountered[ index ] )
            return "duplicates"; 
        end

        encountered[ index ] = true
        min = v if min == nil or v < min
        max = v if max == nil or v > max 
        visited += 1
    end

    if ( max - min + 1 != values.size ) or visited != values.size
        return "hole"
    else
        return "contiguous"
    end

end

tests = [ 
[ false, [ 2,4,5,6 ] ], 
[ false, [ 10,11,13,14 ] ] , 
[ true , [ 20,21,22,23 ] ] , 
[ true , [ 19,20,21,22,23 ] ] ,
[ true , [ 20,21,22,23,24 ] ] ,
[ false, [ 20,21,22,23,24+5 ] ] ,
[ false, [ 2,2,3,4,5 ] ]
]

tests.each do |t|
    result = contiguous( t[1] )
    if( t[0] != ( result == "contiguous" ) )
        puts "Failed Test : " + t[1].to_s + " returned " + result
    end
end

Answer 14

我喜欢 Greg Hewgill 的基数排序思想。要查找重复项，您可以在给定此数组中值的约束的情况下在 O(N) 时间内进行排序。

对于恢复列表原始顺序的就地 O(1) 空间 O(N) 时间，您不必对该数字进行实际交换；你可以用一个标志来标记它：

//Java: assumes all numbers in arr > 1
boolean checkArrayConsecutiveRange(int[] arr) {

// find min/max
int min = arr[0]; int max = arr[0]
for (int i=1; i<arr.length; i++) {
    min = (arr[i] < min ? arr[i] : min);
    max = (arr[i] > max ? arr[i] : max);
}
if (max-min != arr.length) return false;

// flag and check
boolean ret = true;
for (int i=0; i<arr.length; i++) {
    int targetI = Math.abs(arr[i])-min;
    if (arr[targetI] < 0) {
        ret = false; 
        break;
    }
    arr[targetI] = -arr[targetI];
}
for (int i=0; i<arr.length; i++) {
    arr[i] = Math.abs(arr[i]);
}

return ret;
}

将标志存储在给定的数组中是一种欺骗，并且不能很好地与并行化配合使用。我仍在尝试想办法做到这一点，而无需在 O(N) 时间和 O(log N) 空间中接触数组。检查总和和最小二乘之和 (arr[i] - arr.length/2.0)^2 感觉它可能有效。我们所知道的关于没有重复的 0...m 数组的一个定义特征是它是均匀分布的。我们应该检查一下。

现在，只要我能证明这一点。

我想指出，上面涉及阶乘的解决方案需要 O(N) 空间来存储阶乘本身。N！> 2^N，需要 N 个字节来存储。

Answer 15

一个数组包含 N 个数字，您想确定其中两个数字之和是否等于给定数字 K。例如，如果输入是 8,4、1,6，K 是 10，则答案是肯定的（4 和 6 ）。一个数字可以使用两次。请执行下列操作。一个。给出一个 O(N2) 算法来解决这个问题。湾。给出一个 O(N log N) 算法来解决这个问题。（提示：首先对项目进行排序。这样做后，您可以在线性时间内解决问题。） c．对两种解决方案进行编码并比较算法的运行时间。4.

Answer 16

Kent Fredric 的 Ruby 解决方案的AC 版本

（方便测试）

反例（针对 C 版本）：{8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5、18、12、2、9、14、17、21、19、22、15、20、24、11、10、16、25}。这里n=0，m=35。此序列未命中34并有两个2.

它在时间上是 O(m)，在空间上是 O(1)。

在时间 O(n) 和空间 O(1) 中很容易检测到超出范围的值，因此测试集中在范围内（意味着所有值都在有效范围内[n, n+m)）序列。否则{1, 34}是一个反例（对于 C 版本，sizeof(int)==4，数字的标准二进制表示）。

C 和 Ruby 版本之间的主要区别： <<由于 sizeof(int) 有限，​​运算符将旋转 C 中的值，但在 Ruby 中，数字会增长以适应结果，例如，

红宝石：1 << 100 # -> 1267650600228229401496703205376

C：int n = 100; 1 << n // -> 16

在 Ruby 中：check_index ^= 1 << i;相当于check_index.setbit(i). 在 C++ 中可以实现相同的效果：vector<bool> v(m); v[i] = true;

bool isperm_fredric(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     no restriction on n,
     ?overflow?
     a[] may be readonly
   */
  int check_index = 0;
  int check_value = 0;

  int min = a[0];
  for (int i = 0; i < m; ++i) {

    check_index ^= 1 << i;
    check_value ^= 1 << (a[i] - n); //

    if (a[i] < min)
      min = a[i];
  }
  check_index <<= min - n; // min and n may differ e.g., 
                           //  {1, 1}: min=1, but n may be 0.
  return check_index == check_value;
}

上述函数的值已针对以下代码进行了测试：

bool *seen_isperm_trusted  = NULL;
bool isperm_trusted(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(m) in space */

  for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t));
    seen_isperm_trusted[i] = false;

  for (int i = 0; i < m; ++i) {

    if (a[i] < n or a[i] >= n + m)
      return false; // out of range

    if (seen_isperm_trusted[a[i]-n])
      return false; // duplicates
    else
      seen_isperm_trusted[a[i]-n] = true;
  }

  return true; // a[] is a permutation of the range: [n, n+m)
}

输入数组通过以下方式生成：

void backtrack(int m; int a[m], int m, int nitems)
{
  /** generate all permutations with repetition for the range [0, m) */
  if (nitems == m) {
    (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1}
  }
  else for (int i = 0; i < m; ++i) {
      a[nitems] = i;
      backtrack(a, m, nitems + 1);
    }
}

Answer 17

b3的伪代码AC版

（避免对伪代码的误解）

反例：{1, 1, 2, 4, 6, 7, 7}.

int pow_minus_one(int power)
{
  return (power % 2 == 0) ? 1 : -1;
}

int ceil_half(int n)
{
  return n / 2 + (n % 2);
}

bool isperm_b3_3(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     doesn't use n
     possible overflow in sum
     a[] may be readonly
   */
  int altsum = 0;
  int mina = INT_MAX;
  int maxa = INT_MIN;

  for (int i = 0; i < m; ++i)
    {
      const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0
      if (mina > v)
        mina = v;
      if (maxa < v)
        maxa = v;

      altsum += pow_minus_one(v) * v;
    }
  return ((maxa-mina == m-1)
          and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1)
                - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum));
}

Answer 18

def test(a, n, m):
    seen = [False] * m
    for x in a:
        if x < n or x >= n+m:
            return False
        if seen[x-n]:
            return False
        seen[x-n] = True
    return False not in seen

print test([2, 3, 1], 1, 3)
print test([1, 3, 1], 1, 3)
print test([1, 2, 4], 1, 3)

请注意，这只会通过第一个数组，而不考虑not in. :)

我也可以使用 python set，但我选择了set无需考虑性能特征的直接解决方案。

更新：Smashery 指出我错误地解析了“恒定的内存量”，而这个解决方案实际上并没有解决问题。

Answer 19

我目前的最佳选择

def uniqueSet( array )
  check_index = 0; 
  check_value = 0; 
  min = array[0];
  array.each_with_index{ |value,index|
         check_index = check_index ^ ( 1 << index );
         check_value = check_value ^ ( 1 << value );
         min = value if value < min
  } 
  check_index =  check_index  << min;
  return check_index == check_value; 
end

O(n) 和空间 O(1)

我写了一个脚本来蛮力组合，这可能会失败，但它没有找到任何东西。如果您有一个违反此功能的数组，请告知。:)

---

@JF塞巴斯蒂安

它不是真正的哈希算法。从技术上讲，它是一个高效的“已见”值的打包布尔数组。

ci = 0, cv = 0
[5,4,3]{ 
  i = 0 
  v = 5 
  1 << 0 == 000001
  1 << 5 == 100000
  0 ^ 000001  = 000001
  0 ^ 100000  = 100000

  i = 1
  v = 4 
  1 << 1 == 000010
  1 << 4 == 010000
  000001 ^ 000010  = 000011
  100000 ^ 010000  = 110000 

  i = 2
  v = 3 
  1 << 2 == 000100
  1 << 3 == 001000
  000011 ^ 000100  = 000111
  110000 ^ 001000  = 111000 
}
min = 3 
000111 << 3 == 111000
111000 === 111000

这主要是为了“伪造”大多数问题案例，人们使用重复项来做到这一点。在这个系统中，异或会惩罚你两次使用相同的值，并假设你做了 0 次。

这里的警告当然是：

1. $x输入数组长度和最大数组值都受in的最大值限制( 1 << $x > 0 )

2. 最终效果取决于您的底层系统如何实现以下能力：

   1. 右移 1 位 n 位。
   2. 异或 2 个寄存器。（根据实现，“寄存器”可能跨越多个寄存器）

   编辑 注意，上述陈述似乎令人困惑。假设一台完美的机器，其中“整数”是具有无限精度的寄存器，它仍然可以在 O(1) 时间内执行 a ^ b。

但是如果没有这些假设，就必须开始询问简单数学的算法复杂性。

• 1 == 1 有多复杂？肯定每次都应该是 O(1) 吧？
• 2^32 == 2^32 怎么样。
• 奥（1）？2^33 == 2^33？现在您遇到了寄存器大小和底层实现的问题。
• 幸运的是 XOR 和 == 可以并行完成，所以如果一个假设有无限精度并且机器设计为处理无限精度，则可以安全地假设 XOR 和 == 不管它们的值如何都花费恒定的时间（因为它的无限宽度，它将有无限的 0 填充。显然这不存在。而且，将 000000 更改为 000100 并不会增加内存使用量。
• 然而在某些机器上， ( 1 << 32 ) << 1会消耗更多的内存，但有多少是不确定的。

Answer 20

注意：此评论基于问题的原始文本（此后已更正）

如果问题的提出与上面写的完全一样（而且它不仅仅是一个错字）并且对于大小为 n 的数组，如果数组由数字 1...n+1 组成，则函数应该返回（真/假），

...那么答案总是错误的，因为所有数字为 1...n+1 的数组的大小为 n+1 而不是 n。因此这个问题可以在 O(1) 中得到回答。:)

Answer 21

为什么其他解决方案使用每个值的总和？我认为这是有风险的，因为当您将 O(n) 个项目加在一起成为一个数字时，从技术上讲，您使用的空间超过了 O(1) 个。

O(1) 表示不变的空间，不会因 n 的数量而变化。只要它是一个常数，它是1个还是2个变量都没有关系。你为什么说它不仅仅是 O(1) 空间？如果您通过将 n 个数字的总和累积在一个临时变量中来计算它，那么无论如何您都将使用 1 个变量。

在答案中发表评论是因为系统还不允许我写评论。

更新（回复评论）：在这个答案中，我的意思是 O(1) 空间，其中省略了“空间”或“时间”。引用的文本是早期答案的一部分，这是对它的回复。

Answer 22

如果你想知道数字的总和，[n ... n + m - 1]只需使用这个等式。

var sum = m * (m + 2 * n - 1) / 2;

这适用于任何数字，无论是正数还是负数，即使 n 是小数。

Answer 23

鉴于这种 -

编写一个采用大小为 m的int 数组的方法...

我想可以公平地得出结论，m 有一个上限，等于最大int的值（典型值为 2^32）。换句话说，即使 m 未指定为 int，但数组不能有重复项这一事实意味着不能超过 32 位可以形成的值的数量，这反过来意味着 m 是也仅限于 int。

如果这样的结论可以接受，那么我建议使用 (2^33 + 2) * 4 bytes = 34,359,738,376 bytes = 34.4GB 的固定空间来处理所有可能的情况。（不计算输入数组及其循环所需的空间）。

当然，为了优化，我会首先考虑 m，并且只分配实际需要的数量，(2m+2) * 4 字节。

如果这对于 O(1) 空间约束是可以接受的 -对于所述问题- 那么让我继续提出算法建议...... :)

假设： m 个整数的数组，正数或负数，不大于 4 个字节可以容纳的值。重复处理。第一个值可以是任何有效的 int。如上所述限制 m。

首先，创建一个长度为 2m-1 的 int 数组ary，并提供三个 int 变量：left、diff和right。请注意，使 2m+2...

其次，从输入数组中取出第一个值并将其复制到新数组中的 m-1 位置。初始化三个变量。

• 设置ary [m-1] - nthVal // n=0
• 设置左=差异=右= 0

第三，遍历输入数组中的剩余值，并为每次迭代执行以下操作：

• 设置差异= nthVal - ary [m-1]
• if ( diff > m-1 + right || diff < 1-m + left ) return false // 越界
• if ( ary [m-1+ diff ] != null) return false // 重复
• 设置ary [m-1+ diff ] = nthVal
• if ( diff > left ) left = diff // 进一步限制左边界
• if ( diff < right ) right = diff // 将右边界进一步向左约束

我决定把它放在代码中，它起作用了。

这是使用 C# 的工作示例：

public class Program
{
    static bool puzzle(int[] inAry)
    {
        var m = inAry.Count();
        var outAry = new int?[2 * m - 1];
        int diff = 0;
        int left = 0;
        int right = 0;
        outAry[m - 1] = inAry[0];
        for (var i = 1; i < m; i += 1)
        {
            diff = inAry[i] - inAry[0];
            if (diff > m - 1 + right || diff < 1 - m + left) return false;
            if (outAry[m - 1 + diff] != null) return false;
            outAry[m - 1 + diff] = inAry[i];
            if (diff > left) left = diff;
            if (diff < right) right = diff;
        }
        return true;
    }

    static void Main(string[] args)
    {
        var inAry = new int[3]{ 2, 3, 4 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[3] { 21, 31, 41 };
        Console.WriteLine(puzzle(inAry));
        Console.ReadLine();
    }

}

Answer 24

XOR 算法的反例。

（不能作为评论发表）

@popopome

因为a = {0, 2, 7, 5,}它返回true（意味着这a是范围的排列[0, 4)），但false在这种情况下它必须返回（a显然不是 的排列[0, 4)）。

另一个反例：{0, 0, 1, 3, 5, 6, 6}-- 所有值都在范围内，但有重复项。

我可能会错误地实现 popopome 的想法（或测试），因此这里是代码：

bool isperm_popopome(int m; int a[m], int m, int  n)
{
  /** O(m) in time (single pass), O(1) in space,
      no restrictions on n,
      no overflow,
      a[] may be readonly
  */
  int even_xor = 0;
  int odd_xor  = 0;

  for (int i = 0; i < m; ++i)
    {
      if (a[i] % 2 == 0) // is even
        even_xor ^= a[i];
      else
        odd_xor ^= a[i];

      const int b = i + n;
      if (b % 2 == 0)    // is even
        even_xor ^= b;
      else
        odd_xor ^= b;
    }

  return (even_xor == 0) && (odd_xor == 0);
}

Answer 25

在 Python 中：

def ispermutation(iterable, m, n):
    """Whether iterable and the range [n, n+m) have the same elements.

       pre-condition: there are no duplicates in the iterable
    """ 
    for i, elem in enumerate(iterable):
        if not n <= elem < n+m:
            return False

    return i == m-1

print(ispermutation([1, 42], 2, 1)    == False)
print(ispermutation(range(10), 10, 0) == True)
print(ispermutation((2, 1, 3), 3, 1)  == True)
print(ispermutation((2, 1, 3), 3, 0)  == False)
print(ispermutation((2, 1, 3), 4, 1)  == False)
print(ispermutation((2, 1, 3), 2, 1)  == False)

它在时间上是 O(m)，在空间上是 O(1)。它不考虑重复。

替代解决方案：

def ispermutation(iterable, m, n): 
    """Same as above.

    pre-condition: assert(len(list(iterable)) == m)
    """
    return all(n <= elem < n+m for elem in iterable)

Answer 26

所以有一种算法采用 O(n^2)，不需要修改输入数组并占用恒定空间。

首先，假设您知道n和m。这是一个线性操作，因此不会增加任何额外的复杂性。接下来，假设存在一个元素等于n和一个元素等于，n+m-1其余的都在 中[n, n+m)。鉴于此，我们可以将问题简化为包含元素的数组[0, m)。

现在，由于我们知道元素受数组大小的限制，我们可以将每个元素视为一个节点，它具有指向另一个元素的单个链接；换句话说，数组描述了一个有向图。在这个有向图中，如果没有重复元素，则每个节点都属于一个循环，即一个节点可以从自身到达，m或者更少的步长。如果存在重复元素，则存在一个根本无法从其自身到达的节点。

因此，要检测到这一点，您需要从头到尾遍历整个数组，并确定每个元素是否<=m逐步返回自身。如果在步骤中无法访问任何元素<=m，则您有重复并且可以返回 false。否则，当您访问完所有元素时，您可以返回 true：

for (int start_index= 0; start_index<m; ++start_index)
{
    int steps= 1;
    int current_element_index= arr[start_index];
    while (steps<m+1 && current_element_index!=start_index)
    {
        current_element_index= arr[current_element_index];
        ++steps;
    }

    if (steps>m)
    {
        return false;
    }
}

return true;

您可以通过存储其他信息来优化它：

1. 记录每个元素的循环长度之和，除非循环访问该元素之前的元素，否则调用它sum_of_steps。
2. 对于每个元素，仅m-sum_of_steps将节点移出。如果不返回起始元素，也没有访问起始元素之前的元素，则发现循环包含重复元素，可以返回false。

这仍然是 O(n^2)，例如{1, 2, 3, 0, 5, 6, 7, 4}，但它有点快。

Answer 27

如果数组未排序，则来自“nickf”的答案不起作用 var_dump(testArray(array(5, 3, 1, 2, 4), 1, 5)); //给出“重复”！！！！

此外，您计算 sum([n...n+m-1]) 的公式看起来不正确....正确的公式是 (m(m+1)/2 - n(n-1)/2)

Answer 28

这是在 O(N) 时间和 O(1) 额外空间中查找重复项的解决方案：-

public static boolean check_range(int arr[],int n,int m) {

        for(int i=0;i<m;i++) {
            arr[i] = arr[i] - n;
            if(arr[i]>=m)
                return(false);
        }

        System.out.println("In range");

        int j=0;
        while(j<m) {
            System.out.println(j);
            if(arr[j]<m) {

                if(arr[arr[j]]<m) {

                    int t = arr[arr[j]];
                    arr[arr[j]] = arr[j] + m;
                    arr[j] = t;
                    if(j==arr[j]) {

                        arr[j] = arr[j] + m;
                        j++;
                    }

                }

                else return(false);

            }

            else j++;

        }

解释：-

1. 通过 arr[i] = arr[i] - n 将数字带入范围 (0,m-1) 如果超出范围返回 false。
2. 对于每个 i 检查 arr[arr[i]] 是否未被占用，即它的值小于 m
3. 如果是这样，交换(arr[i],arr[arr[i]]) 和 arr[arr[i]] = arr[arr[i]] + m 表示它已被占用
4. 如果 arr[j] = j 并简单地添加 m 并增加 j
5. 如果 arr[arr[j]] >=m 表示它被占用，因此当前值是重复的，因此返回 false。
6. 如果 arr[j] >= m 然后跳过

Answer 29

m个连续数的乘积能被m整除！[m 阶乘]

---

因此，您可以一次性计算 m 个数字的乘积，也可以计算 m！看看乘积是否以 m 为模！在通行证结束时为零

我可能会遗漏一些东西，但这就是我想到的......

在 python 中是这样的

my_list1 = [9,5,8,7,6]

my_list2 = [3,5,4,7]

def 连续（my_list）：

count = 0
prod = fact = 1
for num in my_list:
    prod *= num
    count +=1 
    fact *= count
if not prod % fact: 
    return 1   
else:   
    return 0 

连续打印（my_list1）

连续打印（my_list2）

---

HotPotato ~$ python m_consecutive.py

1

0

Answer 30

我提出以下建议：

选择一组有限的素数 P_1,P_2,...,P_K，并以每个 P_i 为模计算输入序列中元素的出现次数（减去最小值）。有效序列的模式是已知的。

例如，对于 17 个元素的序列，模 2 我们必须具有轮廓：[9 8]，模 3：[6 6 5]，模 5：[4 4 3 3 3]，等等。

结合使用多个基础的测试，我们获得了越来越精确的概率测试。由于条目受整数大小的限制，因此存在提供精确测试的有限基。这类似于概率伪素性测试。

S_i is an int array of size P_i, initially filled with 0, i=1..K
M is the length of the input sequence
Mn = INT_MAX
Mx = INT_MIN

for x in the input sequence:
  for i in 1..K: S_i[x % P_i]++  // count occurrences mod Pi
  Mn = min(Mn,x)  // update min
  Mx = max(Mx,x)  // and max

if Mx-Mn != M-1: return False  // Check bounds

for i in 1..K:
  // Check profile mod P_i
  Q = M / P_i
  R = M % P_i
  Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1
  if this test fails, return False

return True

Answer 31

如果数字是正数，有一个简单的解决方案可以一次性使用 O(1) 空间：

int max = arr[0];
int min = arr[0];
for (int i = 0; i < n; i++) {
    int x = abs(arr[i]);
    int y = x % n;
    if (arr[y] < 0)
        return false;
    arr[y] = -arr[y];
    if (x > max)
        max = x;
    else if (x < min)
        min = x;
}
return max - min == n - 1;

Answer 32

我想问题归结为确保

(maximum - minimum + 1) == array_size

这显然可以在 O(N) 时间和 O(1) 空间中完成，如下所示：

int check_range(int input[], int N){
    int max = -INFINITY, min = INFINITY, i;
    for(i=0; i<N; i++){
        if(input[i] < min) min=input[i];
        if(input[i] > max) max=input[i];
    }
    return (max - min + 1) == N;
}

请注意，此方法考虑了重复的可能性。请报告解决方案中的任何差异。

Answer 33

如何分别对偶数和奇数使用 XOR。考虑位级别而不是整数值本身。

bool is_same(const int* a, const int* b, int len)
{
    int even_xor = 0; 
    int odd_xor = 0;

    for(int i=0;i<len;++i)
    {
        if(a[i] & 0x01) odd_xor ^= a[i];
        else even_xor ^= a[i];

        if(b[i] & 0x01) odd_xor ^= b[i];
        else even_xor ^= b[i];
    }

    return (even_xor == 0) && (odd_xor == 0);
}

Answer 34

时间线性，空间常数解int m

恒定空间是通过利用符号位来实现的。如果小于ie，则可以对任何可变int范围执行此操作，即当输入范围可以转移到范围（如果不是正数）时。在实践中，如果输入是可变的，前提条件几乎总是正确的。mINT_MAX[n, n+m)[1, m+1)n

/** gcc -std=c99 ... */
#include <assert.h>
#include <iso646.h>  // and, or
#include <limits.h>  // INT_MIN
#include <stdbool.h> // bool
#include <stdlib.h>  // abs()

bool inrange(int m; int a[m], int m, int n)
{
  /** Whether min(a[]) == n and max(a[]) == n+(m-1)
  */
  if (m == 0) return true; // empty range is a valid range

  // check out-of-range values
  int max = INT_MIN, min = INT_MAX;
  for (int i = 0; i < m; ++i) {
    if (min > a[i]) min = a[i];
    if (max < a[i]) max = a[i];
  }
  return (min == n and max == n+(m-1));
}

bool isperm_minus2(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')

      Whether a[] is a permutation of the range [n, n+m).

      feature: It marks visited items using a sign bit.
  */
  if (not inrange(a, m, n))
    return false; // out of range

  assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
  for (int *p = a; p != &a[m]; ++p) {
    *p -= (n - 1); // [n, n+m) -> [1, m+1)
    assert(*p > 0);
  }

  // determine: are there duplicates
  bool has_duplicates = false;
  for (int i = 0; i < m; ++i) {
    const int j = abs(a[i]) - 1;
    assert(j >= 0);
    assert(j < m);
    if (a[j] > 0)
      a[j] *= -1; // mark
    else { // already seen
      has_duplicates = true;
      break;
    }
  }

  // restore the array
  for (int *p = a; p != &a[m]; ++p) {
    if (*p < 0) 
      *p *= -1; // unmark
    // [1, m+1) -> [n, n+m)
    *p += (n - 1);        
  }

  return not has_duplicates; // no duplicates? (+ inrange)
}

Answer 35

似乎我们可以通过将所有数字 n...n+m 相乘来检查重复项，然后将该值与没有重复项m!/(n-1)! 的序列的预期乘积进行比较！（请注意，这假定序列不可能同时通过预期总和测试和预期乘积测试）。

因此，添加到hazzen 的伪代码中，我们有：

is_range(int[] nums, int n, int m) {
  sum_to_m := (m * (m + 1)) / 2
  expected_sum := sum_to_m - (n * (n - 1)) / 2
  real_sum := sum(nums)
  expected_product := m! / (n - 1)!
  real_product := product(nums)
  return ((real_sum == expected_sum) && (expected_product == real_product))

编辑：这是我在 Java 中使用平方和检查重复项的解决方案。它还通过将序列从 1 开始来处理任何范围（包括负数）。

// low must be less than high
public boolean isSequence(int[] nums, int low, int high) {
    int shift = 1 - low;
    low += shift;
    high += shift;

    int sum = 0;
    int sumSquares = 0;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i] + shift;

        if (num < low)
            return false;
        else if (num > high)
            return false;

        sum += num;
        sumSquares += num * num;
    }

    int expectedSum = (high * (high + 1)) / 2;

    if (sum != expectedSum)
        return false;

    int expectedSumSquares = high * (high + 1) * (2 * high + 1) / 6;

    if (sumSquares != expectedSumSquares)
        return false;

    return true;
}

Answer 36

如果这是一个错字，并且问题是所有数字都在 1...n 范围内，那么：

def try_arr(arr):
    n = len(arr)
    return (not any(x<1 or x>n for x in arr)) and sum(arr)==n*(n+1)/2

$ print try_arr([1,2,3])
True

$ print try_arr([1,3,1])
False

$ print try_arr([1,2,4])
False

笔记：

• 我使用的是数字从 1 开始的原始版本的定义。当然可以修改代码以说明从另一个数字开始。

• 如果数组 (n) 的大小已知，您可以修改它以从例如输入文件流式传输数据，并且几乎不使用内存（sum() 中的 1 个临时变量和从流中获取的当前项目的 1 个变量）

• any() 在 python 2.5 中是新的（但在早期版本的 python 中你有其他方法来表达同样的事情）

• 它使用 O(n) 时间 O(1) 空间。（更新：我写它确实考虑了重复，但显然这不是真的，正如对此处另一个答案的评论所证明的那样）。

Answer 37

Fail := False;
Sum1 := 0;
Sum2 := 0;
TSum1 := 0;
TSum2 := 0;

For i := 1 to m do
  Begin
    TSum1 := TSum1 + i;
    TSum2 := TSum2 + i * i;
    Item := Array[i] - n;
    If (Item < 0) or (Item >= m) then 
      Fail := True
    Else 
      Begin
        Sum1 := Sum1 + Item;
        Sum2 := Sum2 + Item * Item;
      End;
  End;
Fail := Fail Or (Sum1 <> TSum1) or (Sum2 <> TSum2);

累了，没有编译器，但我认为这给了 O(m) 运行时间并且不能被愚弄。

Answer 38

我认为我在原始帖子中没有很好地解释自己（在实线下方）。例如，对于 [1 2 3 4 5] 的输入，算法计算总和：

-1 + 2 - 3 + 4 - 5 

这应该等于

-1^5 * ceil(5/2)

下面的伪代码显示了如何检查不从 1 开始的向量。 该算法处理输入向量未排序和/或包含重复项的情况。

---

以下算法通过计算向量元素的交替和来解决该问题：

-1 + 2 - 3 + 4 - 5 + .... + m = (-1)^m * ceil(m/2)

其中ceil向上舍入到最接近的整数。换句话说，奇数从运行总数中减去，偶数被添加到它。

function test(data, m)
    altSum = 0
    n = Inf
    mCheck = -Inf
    for ii = 1:m
    {
        if data(ii) < n
            n = data(ii)
        if data(ii) > mCheck
            mCheck = data(ii)
        altSum = altSum + (-1)^data(ii) * data(ii)
    }
    if ((mCheck-n+1!=m) || (-1)^(n+m-1) * ceil((n+m-1)/2) - ((-1)^(n-1) * ceil((n-1)/2)) != altSum
        return false
    else
        return true

Answer 39

我认为您根本不需要使用总和。只需检查最小值和最大值并检查是否有欺骗性。检查欺骗是较难的部分，因为您事先不知道 n，因此您无法一次性排序。要解决这个问题，请放宽 (edit:destination) 数组的条件。不需要对其进行排序，而是对已排序的序列进行循环移位，以便数组变为 [k,k+1,..., n+m-2, n+m-1,n,n+ 1, ... ,k-2,k-1] 对于一些 k。

使用上述条件，您可以假设 a[0] 已经在正确的位置，那么元素的正确位置d是(d-a[0]) mod m，假设从零开始的数组索引。例如，使用 [4,?,?,?] 您可以预期 [4,5,6,7] 或 [4,1,2,3] 或 [4,5,6,3] 或 [4,5, 2,3]。

然后只需扫描一次数组，将每个元素放在其计算的位置，更新最小值和最大值并检查冲突。如果没有冲突且max-min=m，则条件成立，否则为假。