时间和O(1)空间)
题目给一个整数数组要找没有出现过的最小正整数。比如[-5,3,2,3]1没出现答案就是1[1,2,3]里面前三个正整数都有了答案是4。负数不参与这次查找重复出现也只算出现过。我先想到做一张出现表读到正整数x就标记x出现过。最后从1开始看哪个没标记就返回哪个。我还想过用一个min记着当前最小缺失值。比如[-5,3,2,3,1]先遇到3和2min仍是1直到最后遇到1才连续跳过已经出现的1、2、3到4。这样确实能做。但如果数组里有一个特别大的正数表也要开到那么大吗不用。数组只有n个位置。如果1到n都出现了正好已经占满这些位置最小缺失值就是n1如果没有全出现缺的那个就在1到n里。所以只用记录1到n。0、负数和大于n的数可以忽略。这个办法时间O(n)另开出现表要O(n)空间。min有时一口气走很多步但它只向前、不回退累计也就是线性移动。原题要求时间尽可能高效并没有额外规定必须常数空间。原数组读过的位置能不能拿来标记我不太想再开一个数组。原数组本身有n个格子而我们恰好只需要记录n个正整数能不能直接借这些格子约定数字1对应下标0数字2对应下标1数字x对应下标x-1。往对应格子写一个标记就表示这个数出现过。这里不是说第一个格子原来必须存1。我们只是重新分配它的用途以后用第一格回答“1见过吗”用第二格回答“2见过吗”。原数组可能乱序格子里的旧数与这个新用途没有关系。先拿[3,1,2]试试。读到3要去下标2写标记。可那个位置原来是2这个2也得处理直接覆盖它就丢了。如果这时不管2直接写标记我们知道3出现过了却再也不能从那格读到原来的2。这就是还需要解决的问题借用格子不等于可以丢掉它原来存的数。所以我想到写之前先把2拿出来暂存在一个变量里。写完3的标记再处理手里的2。后面还挤出别的数就继续拿住、继续处理。我们先用-1表示“出现过”把这个过程走完输入本来就有负数怎么办后面再补。手里这个数一次次变成了什么先从下标0取出3放到变量x里。原来的格子改成0表示这个值已经取走了。现在要记录3去的是第三格也就是下标2。那里原来存着2。先别覆盖用displaced把这个旧值复制出来这时数组还没改手里的x也仍是3。然后才把第三格写成-1表示3已经出现。数组变成[0,1,-1]。当前的3记录完了下一步处理谁处理刚保住的2所以把displaced交给x令x变成2。接着记录2。它对应下标1那里原来是1。先拿住1再写-1。数组变成[0,-1,-1]手里变成1。最后记录1。它对应下标0那里已经是0。写成-1拿到的旧值是0不用再追下去了。做完哪一步数组手里的x从下标0取出3[0,1,2]3标记3拿走旧值2[0,1,-1]2标记2拿走旧值1[0,-1,-1]1标记1拿到0[-1,-1,-1]0停止这时数组不再保存原来的排列而是保存出现情况三个格子都是-1说明1、2、3都出现过答案是4。那后面还有一个7谁来处理我当时对只举三元素的例子还不放心如果后面还有别的数呢所以这里需要分清两个循环。内层while只追当前手里这串被挤出的数外层for还要继续检查数组后面的格子。比如换成[3,1,2,7,1,2,3]长度是7。前面那串处理完只标记了1、2、3后面的7还在那里前三个处理后[-1,-1,-1,7,1,2,3] 外层走到7 [-1,-1,-1,0,1,2,-1]手里拿到旧值33已经标记过这串就停。但外层还会继续走到后面的1和2把它们取走发现各自已经记录过也停止。最终是[-1,-1,-1,0,0,0,-1]。下标3没有标记表示4没出现返回4。已经是-1的格子要直接跳过。它存的是我们留下的出现信息不能再清成0否则刚记好的信息又被擦掉了。原来就有-1还有重复值怎么办刚才先用了-1当标记但题目允许原数组出现-1。如果输入是[-1,2]第一个格子本来就是-1并不表示1出现过。解决这件事不需要找一个更稀奇的标记。我们前面已经知道只有1到n需要保留。先把范围外的原值全部清成0原始-1也就没了。以后出现的-1只可能是程序写入的。[-1,2]先变成[0,2]再记录2结果是[0,-1]。第一个格子仍没有标记所以答案正确地是1。重复值也不用反复记录。比如拿到第二个2发现下标1已经是-1说明2的出现信息早就留下了直接停。手里的重复2不再有新的作用。对着上面的过程看代码displaced就是每次先拿走的旧值int firstMissingMark(int A[], int n) { // 消除原始 -1 与标记 -1 的歧义范围外数据也无须考虑 for (int i 0; i n; i) { if (A[i] 0 || A[i] n) A[i] 0; } for (int i 0; i n; i) { if (A[i] -1) continue; // 此位置已被标记 int x A[i]; A[i] 0; // 取走当前值释放当前位置 while (x 1 x n A[x - 1] ! -1) { int displaced A[x - 1]; A[x - 1] -1; // 记录 x 已出现 x displaced; // 处理被挤出来的旧值 } } for (int i 0; i n; i) if (A[i] ! -1) return i 1; return n 1; }代码先检查x是否在1到n再访问A[x-1]。手里拿到0时条件就不成立不会去访问下标-1。while会不会把时间变成平方看内层每次真正做了什么找到一个还没标记的格子把它变成-1。这个标记以后不会取消目标格已经是-1时也不会继续处理。整个数组只有n格因此所有内层循环加起来成功标记最多n次并不是每个外层位置都能再跑n次。加上预处理、外层扫描和最后查缺总时间仍是O(n)。手里只暂存固定数量的值没有再开数组额外空间O(1)。交换法是另一种安置旧值的办法前面我把旧值拿在手里。还有一种常见做法是让数字x到A[x-1]同时把那里的旧值换回当前格子继续处理。同样从[3,1,2]开始3和下标2的2交换得到[2,1,3]再把当前的2和下标1的1交换得到[1,2,3]。它用“对应格子里就是这个数”表示出现过而不是写-1int firstMissingSwap(int A[], int n) { for (int i 0; i n; i) { while (A[i] 1 A[i] n A[i] ! A[A[i] - 1]) { int x A[i]; int temp A[x - 1]; A[x - 1] x; A[i] temp; } } for (int i 0; i n; i) if (A[i] ! i 1) return i 1; return n 1; }这里要留意重复值。[2,2,1]中第一个2想去的位置已经是2再交换数组不会变化继续while就停不下来。所以先判断目标位置是否已经是同一个数。每次有效交换都会让一个尚未归位的位置存好对应的数已归位的位置不会被有效交换破坏。总有效交换次数也是O(n)。两种办法都修改输入。区别在于被挤出的值放哪里一个交给临时变量一个换回当前格子。完整验证会把它们与另开出现表的参照分别比较。这两份C实现约定0≤nINT_MAXn大于0时数组有效空数组返回1。若为了保留输入而复制整个数组复制占用的空间要另外算。题意按2018年408原卷第41题整理原卷来自厦门工学院公开备考资料。下面保留我的解题复盘C实现与验证是补充不是官方答案。附录完整验证程序参照在未修改的输入上从1逐个找缺失值两种原地算法分别复制输入后运行。[-1,2]、[2,2,1]等情形都在原有穷举域内。完整程序包含上面的题解函数和独立参照。保留源码是为了读者能自己改输入、定位错误不需要先读完它才能理解正文。gcc -stdc11 -Wall -Wextra -Werror -pedantic -fsanitizeaddress,undefined -fno-omit-frame-pointer lab.c -o lab ./lab#include assert.h #include limits.h #include stdbool.h #include stddef.h #include stdio.h #include stdlib.h int firstMissingSwap(int A[], int n) { for (int i 0; i n; i) { while (A[i] 1 A[i] n A[i] ! A[A[i] - 1]) { int x A[i]; int temp A[x - 1]; A[x - 1] x; A[i] temp; } } for (int i 0; i n; i) if (A[i] ! i 1) return i 1; return n 1; } int firstMissingMark(int A[], int n) { // 消除原始 -1 与标记 -1 的歧义范围外数据也无须考虑 for (int i 0; i n; i) { if (A[i] 0 || A[i] n) A[i] 0; } for (int i 0; i n; i) { if (A[i] -1) continue; // 此位置已被标记 int x A[i]; A[i] 0; // 取走当前值释放当前位置 while (x 1 x n A[x - 1] ! -1) { int displaced A[x - 1]; A[x - 1] -1; // 记录 x 已出现 x displaced; // 处理被挤出来的旧值 } } for (int i 0; i n; i) if (A[i] ! -1) return i 1; return n 1; } int missingOracle(const int a[], int n) { for (int candidate 1; candidate n 1; candidate) { int found 0; for (int i 0; i n; i) if (a[i] candidate) found 1; if (!found) return candidate; } abort(); } unsigned rng_state 4082018; unsigned rnd(void) { rng_state rng_state * 1664525u 1013904223u; return rng_state; } void verify(const int a[], int n) { int b[96], c[96]; for (int i 0; i n; i) b[i] c[i] a[i]; int expected missingOracle(a, n); assert(firstMissingSwap(b, n) expected); assert(firstMissingMark(c, n) expected); } int main(void) { size_t cases 0; int duplicate[3] {2, 2, 1}; verify(duplicate, 3); const int alphabet[8] {INT_MIN, -1, 0, 1, 2, 3, 6, INT_MAX}; for (int n 0; n 6; n) { size_t total 1; for (int i 0; i n; i) total * 8; for (size_t mask 0; mask total; mask) { int a[96]; size_t x mask; for (int i 0; i n; i) { a[i] alphabet[x % 8]; x / 8; } verify(a, n); cases; } } for (int trial 0; trial 10000; trial) { int a[96], n (int)(rnd() % 97); for (int i 0; i n; i) a[i] (int)(rnd() % 150) - 25; verify(a, n); cases; } printf(PASS missing cases%zu\n, cases); return 0; }这次改写后重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序309593组数组与边界检查通过输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。PASS missing cases309593有限测试是发现错误的证据不代替正文的正确性与复杂度理由。 
长河君 · 2026/10/18 5:59:00 · 阅读 1.2k 最小缺失正整数：我的暂存标记法，怎样做到O(n)时间和O(1)空间
题目给一个整数数组要找没有出现过的最小正整数。比如[-5,3,2,3]1没出现答案就是1[1,2,3]里面前三个正整数都有了答案是4。负数不参与这次查找重复出现也只算出现过。我先想到做一张出现表读到正整数x就标记x出现过。最后从1开始看哪个没标记就返回哪个。我还想过用一个min记着当前最小缺失值。比如[-5,3,2,3,1]先遇到3和2min仍是1直到最后遇到1才连续跳过已经出现的1、2、3到4。这样确实能做。但如果数组里有一个特别大的正数表也要开到那么大吗不用。数组只有n个位置。如果1到n都出现了正好已经占满这些位置最小缺失值就是n1如果没有全出现缺的那个就在1到n里。所以只用记录1到n。0、负数和大于n的数可以忽略。这个办法时间O(n)另开出现表要O(n)空间。min有时一口气走很多步但它只向前、不回退累计也就是线性移动。原题要求时间尽可能高效并没有额外规定必须常数空间。原数组读过的位置能不能拿来标记我不太想再开一个数组。原数组本身有n个格子而我们恰好只需要记录n个正整数能不能直接借这些格子约定数字1对应下标0数字2对应下标1数字x对应下标x-1。往对应格子写一个标记就表示这个数出现过。这里不是说第一个格子原来必须存1。我们只是重新分配它的用途以后用第一格回答“1见过吗”用第二格回答“2见过吗”。原数组可能乱序格子里的旧数与这个新用途没有关系。先拿[3,1,2]试试。读到3要去下标2写标记。可那个位置原来是2这个2也得处理直接覆盖它就丢了。如果这时不管2直接写标记我们知道3出现过了却再也不能从那格读到原来的2。这就是还需要解决的问题借用格子不等于可以丢掉它原来存的数。所以我想到写之前先把2拿出来暂存在一个变量里。写完3的标记再处理手里的2。后面还挤出别的数就继续拿住、继续处理。我们先用-1表示“出现过”把这个过程走完输入本来就有负数怎么办后面再补。手里这个数一次次变成了什么先从下标0取出3放到变量x里。原来的格子改成0表示这个值已经取走了。现在要记录3去的是第三格也就是下标2。那里原来存着2。先别覆盖用displaced把这个旧值复制出来这时数组还没改手里的x也仍是3。然后才把第三格写成-1表示3已经出现。数组变成[0,1,-1]。当前的3记录完了下一步处理谁处理刚保住的2所以把displaced交给x令x变成2。接着记录2。它对应下标1那里原来是1。先拿住1再写-1。数组变成[0,-1,-1]手里变成1。最后记录1。它对应下标0那里已经是0。写成-1拿到的旧值是0不用再追下去了。做完哪一步数组手里的x从下标0取出3[0,1,2]3标记3拿走旧值2[0,1,-1]2标记2拿走旧值1[0,-1,-1]1标记1拿到0[-1,-1,-1]0停止这时数组不再保存原来的排列而是保存出现情况三个格子都是-1说明1、2、3都出现过答案是4。那后面还有一个7谁来处理我当时对只举三元素的例子还不放心如果后面还有别的数呢所以这里需要分清两个循环。内层while只追当前手里这串被挤出的数外层for还要继续检查数组后面的格子。比如换成[3,1,2,7,1,2,3]长度是7。前面那串处理完只标记了1、2、3后面的7还在那里前三个处理后[-1,-1,-1,7,1,2,3] 外层走到7 [-1,-1,-1,0,1,2,-1]手里拿到旧值33已经标记过这串就停。但外层还会继续走到后面的1和2把它们取走发现各自已经记录过也停止。最终是[-1,-1,-1,0,0,0,-1]。下标3没有标记表示4没出现返回4。已经是-1的格子要直接跳过。它存的是我们留下的出现信息不能再清成0否则刚记好的信息又被擦掉了。原来就有-1还有重复值怎么办刚才先用了-1当标记但题目允许原数组出现-1。如果输入是[-1,2]第一个格子本来就是-1并不表示1出现过。解决这件事不需要找一个更稀奇的标记。我们前面已经知道只有1到n需要保留。先把范围外的原值全部清成0原始-1也就没了。以后出现的-1只可能是程序写入的。[-1,2]先变成[0,2]再记录2结果是[0,-1]。第一个格子仍没有标记所以答案正确地是1。重复值也不用反复记录。比如拿到第二个2发现下标1已经是-1说明2的出现信息早就留下了直接停。手里的重复2不再有新的作用。对着上面的过程看代码displaced就是每次先拿走的旧值int firstMissingMark(int A[], int n) { // 消除原始 -1 与标记 -1 的歧义范围外数据也无须考虑 for (int i 0; i n; i) { if (A[i] 0 || A[i] n) A[i] 0; } for (int i 0; i n; i) { if (A[i] -1) continue; // 此位置已被标记 int x A[i]; A[i] 0; // 取走当前值释放当前位置 while (x 1 x n A[x - 1] ! -1) { int displaced A[x - 1]; A[x - 1] -1; // 记录 x 已出现 x displaced; // 处理被挤出来的旧值 } } for (int i 0; i n; i) if (A[i] ! -1) return i 1; return n 1; }代码先检查x是否在1到n再访问A[x-1]。手里拿到0时条件就不成立不会去访问下标-1。while会不会把时间变成平方看内层每次真正做了什么找到一个还没标记的格子把它变成-1。这个标记以后不会取消目标格已经是-1时也不会继续处理。整个数组只有n格因此所有内层循环加起来成功标记最多n次并不是每个外层位置都能再跑n次。加上预处理、外层扫描和最后查缺总时间仍是O(n)。手里只暂存固定数量的值没有再开数组额外空间O(1)。交换法是另一种安置旧值的办法前面我把旧值拿在手里。还有一种常见做法是让数字x到A[x-1]同时把那里的旧值换回当前格子继续处理。同样从[3,1,2]开始3和下标2的2交换得到[2,1,3]再把当前的2和下标1的1交换得到[1,2,3]。它用“对应格子里就是这个数”表示出现过而不是写-1int firstMissingSwap(int A[], int n) { for (int i 0; i n; i) { while (A[i] 1 A[i] n A[i] ! A[A[i] - 1]) { int x A[i]; int temp A[x - 1]; A[x - 1] x; A[i] temp; } } for (int i 0; i n; i) if (A[i] ! i 1) return i 1; return n 1; }这里要留意重复值。[2,2,1]中第一个2想去的位置已经是2再交换数组不会变化继续while就停不下来。所以先判断目标位置是否已经是同一个数。每次有效交换都会让一个尚未归位的位置存好对应的数已归位的位置不会被有效交换破坏。总有效交换次数也是O(n)。两种办法都修改输入。区别在于被挤出的值放哪里一个交给临时变量一个换回当前格子。完整验证会把它们与另开出现表的参照分别比较。这两份C实现约定0≤nINT_MAXn大于0时数组有效空数组返回1。若为了保留输入而复制整个数组复制占用的空间要另外算。题意按2018年408原卷第41题整理原卷来自厦门工学院公开备考资料。下面保留我的解题复盘C实现与验证是补充不是官方答案。附录完整验证程序参照在未修改的输入上从1逐个找缺失值两种原地算法分别复制输入后运行。[-1,2]、[2,2,1]等情形都在原有穷举域内。完整程序包含上面的题解函数和独立参照。保留源码是为了读者能自己改输入、定位错误不需要先读完它才能理解正文。gcc -stdc11 -Wall -Wextra -Werror -pedantic -fsanitizeaddress,undefined -fno-omit-frame-pointer lab.c -o lab ./lab#include assert.h #include limits.h #include stdbool.h #include stddef.h #include stdio.h #include stdlib.h int firstMissingSwap(int A[], int n) { for (int i 0; i n; i) { while (A[i] 1 A[i] n A[i] ! A[A[i] - 1]) { int x A[i]; int temp A[x - 1]; A[x - 1] x; A[i] temp; } } for (int i 0; i n; i) if (A[i] ! i 1) return i 1; return n 1; } int firstMissingMark(int A[], int n) { // 消除原始 -1 与标记 -1 的歧义范围外数据也无须考虑 for (int i 0; i n; i) { if (A[i] 0 || A[i] n) A[i] 0; } for (int i 0; i n; i) { if (A[i] -1) continue; // 此位置已被标记 int x A[i]; A[i] 0; // 取走当前值释放当前位置 while (x 1 x n A[x - 1] ! -1) { int displaced A[x - 1]; A[x - 1] -1; // 记录 x 已出现 x displaced; // 处理被挤出来的旧值 } } for (int i 0; i n; i) if (A[i] ! -1) return i 1; return n 1; } int missingOracle(const int a[], int n) { for (int candidate 1; candidate n 1; candidate) { int found 0; for (int i 0; i n; i) if (a[i] candidate) found 1; if (!found) return candidate; } abort(); } unsigned rng_state 4082018; unsigned rnd(void) { rng_state rng_state * 1664525u 1013904223u; return rng_state; } void verify(const int a[], int n) { int b[96], c[96]; for (int i 0; i n; i) b[i] c[i] a[i]; int expected missingOracle(a, n); assert(firstMissingSwap(b, n) expected); assert(firstMissingMark(c, n) expected); } int main(void) { size_t cases 0; int duplicate[3] {2, 2, 1}; verify(duplicate, 3); const int alphabet[8] {INT_MIN, -1, 0, 1, 2, 3, 6, INT_MAX}; for (int n 0; n 6; n) { size_t total 1; for (int i 0; i n; i) total * 8; for (size_t mask 0; mask total; mask) { int a[96]; size_t x mask; for (int i 0; i n; i) { a[i] alphabet[x % 8]; x / 8; } verify(a, n); cases; } } for (int trial 0; trial 10000; trial) { int a[96], n (int)(rnd() % 97); for (int i 0; i n; i) a[i] (int)(rnd() % 150) - 25; verify(a, n); cases; } printf(PASS missing cases%zu\n, cases); return 0; }这次改写后重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序309593组数组与边界检查通过输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。PASS missing cases309593有限测试是发现错误的证据不代替正文的正确性与复杂度理由。