一、面试问题

给定一个包含正数和负数的无序数组，找出数组中缺失的最小正整数。

示例 1：

  • 输入：arr[] = [2, -3, 4, 1, 1, 7]
  • 输出：3
  • 解释：3 是数组中缺失的最小正整数。

示例 2：

  • 输入：arr[] = [5, 3, 2, 5, 1]
  • 输出：4
  • 解释：4 是数组中缺失的最小正整数。

示例 3：

  • 输入：arr[] = [-8, 0, -1, -4, -3]
  • 输出：1
  • 解释：1 是数组中缺失的最小正整数。

二、【朴素解法】排序法 —— 时间复杂度 O (n*log n)，空间复杂度 O (1)

(一) 解法思路

先对数组排序，并假设缺失的数字为 1。随后遍历数组，对每个元素 arr [i] 执行以下判断：

  • 如果 arr [i] 等于缺失数字，则将缺失数字加 1。
  • 如果 arr [i] 小于缺失数字，则继续查找缺失数字。
  • 如果 arr [i] 大于缺失数字，则终止遍历并返回当前缺失数字。

(二) 使用6种语言实现

1. C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int missingNumber(vector<int> &arr) {

    sort(arr.begin(), arr.end());
    int res = 1;
    for (int i = 0; i < arr.size(); i++) {

        // 如果我们在数组中找到了 'res'，
        // 说明 'res' 不是缺失的数字，因此将其加 1
        if (arr[i] == res) 
            res++;

            // 如果当前元素大于 'res'，
            // 说明 'res' 无法在数组中找到，
            // 因此它就是我们最终的答案
        else if (arr[i] > res) 
            break;
    }
    return res;
}

int main() {
    vector<int> arr = {2, -3, 4, 1, 1, 7};

    cout << missingNumber(arr);
    return 0;
}

2. C

#include <stdio.h>

int cmp(const int *a, const int *b) {
    return (*a - *b);
}

int missingNumber(int arr[], int size) {

    // 对数组进行排序
    qsort(arr, size, sizeof(int), (int(*)(const void*, const void*))cmp);

    // res 用于存储当前缺失的最小正整数，
    // 初始值设为 1
    int res = 1;
    for (int i = 0; i < size; i++) {

        // 如果我们在数组中找到了 'res'，
        // 说明 'res' 不是缺失的数字，因此将其加 1
        if (arr[i] == res) {
            res++;
        }

        // 如果当前元素大于 'res'，
        // 说明 'res' 无法在数组中找到，
        // 因此它就是我们最终的答案
        else if (arr[i] > res) {
            break;
        }
    }
    return res;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("%d", missingNumber(arr, size));
    return 0;
}

3. Java

import java.util.Arrays;
class DSA {

    static int missingNumber(int[] arr) {
        Arrays.sort(arr);

        // res 用于存储当前缺失的最小正整数，
        // 初始值设为 1
        int res = 1;
        for (int i = 0; i < arr.length; i++) {

            // 如果我们在数组中找到了 'res'，
            // 说明 'res' 不是缺失的数字，因此将其加 1
            if (arr[i] == res) {
                res++;
            }

                // 如果当前元素大于 'res'，
                // 说明 'res' 无法在数组中找到，
                // 因此它就是我们最终的答案
            else if (arr[i] > res) {
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

4. Python

def missingNumber(arr):
    arr.sort()

    # res 用于存储当前缺失的最小正整数，
    # 初始值设为 1
    res = 1
    for num in arr:

        # 如果我们在数组中找到了 'res'，
        # 说明 'res' 不是缺失的数字，因此将其加 1
        if num == res:
            res += 1

        # 如果当前元素大于 'res'，
        # 说明 'res' 无法在数组中找到，
        # 因此它就是我们最终的答案
        elif num > res:
            break
    return res


if __name__ == "__main__":

    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

5. C#

using System;
class DSA {

    static int missingNumber(int[] arr) {
        Array.Sort(arr);

        // res 用于存储当前缺失的最小正整数，
        // 初始值设为 1
        int res = 1;
        for (int i = 0; i < arr.Length; i++) {

            // 如果我们在数组中找到了 'res'，
            // 说明 'res' 不是缺失的数字，因此将其加 1
            if (arr[i] == res) {
                res++;
            }

            // 如果当前元素大于 'res'，
            // 说明 'res' 无法在数组中找到，
            // 因此它就是我们最终的答案
            else if (arr[i] > res) {
                break;
            }
        }
        return res;
    }

    static void Main(string[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        Console.WriteLine(missingNumber(arr));
    }
}

6. JavaScript

function missingNumber(arr) {
  arr.sort((a, b) => a - b);

  // res 用于存储当前缺失的最小正整数，
  // 初始值设为 1
  let res = 1;
  for (let i = 0; i < arr.length; i++) {

    // 如果我们在数组中找到了 'res'，
    // 说明 'res' 不是缺失的数字，因此将其加 1
    if (arr[i] == res) {
      res++;
    }

      // 如果当前元素大于 'res'，
      // 说明 'res' 无法在数组中找到，
      // 因此它就是我们最终的答案
    else if (arr[i] > res) {
      break;
    }
  }
  return res;
}

const arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

(三) 代码输出和算法复杂度

输出：

3

时间复杂度：O(n*log n)

空间复杂度：O(1)

三、【优化解法】使用标记数组（访问数组）实现 —— 时间复杂度 O (n)，空间复杂度 O (n)

(一) 解法思路

创建一个标记 / 访问数组，用于记录原始数组中哪些数字是存在的。遍历输入数组，对其中的每一个正整数，我们在访问数组中标记它对应的位置。标记完成后，遍历访问数组，找到第一个未被标记的位置。这个未被访问的下标，就是我们要找的最小缺失正整数。

注意：我们只标记 1 到 n 范围内的数字。

(二) 使用6种语言实现

1. C++

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int> &arr) {
    int n = arr.size();

    // 用于标记元素是否出现过
    vector<bool> vis(n, false);
    for (int i = 0; i < n; i++) {

        // 如果元素在 1 到 n 的范围内
        // 就将其标记为已访问
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = true;
    }

    // 查找原始数组中第一个未被访问的元素
    for (int i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            return i;
        }
    }

    // 如果 1 到 n 的所有元素都已访问
    // 那么 n + 1 就是第一个缺失的正整数
    return n + 1;
}

int main() {

    vector<int> arr = {2, -3, 4, 1, 1, 7};
    cout << missingNumber(arr);
}

2. C

#include <stdio.h>

int missingNumber(int *arr, int n) {
    
    // 用于标记元素是否出现过
    int *vis = (int *)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        
        // 如果元素在 1 到 n 的范围内
        // 就将其标记为已访问
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = 1;
    }

    // 查找原始数组中第一个未被访问的元素
    for (int i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            free(vis);
            return i;
        }
    }

    // 如果 1 到 n 的所有元素都已访问
    // 那么 n+1 就是第一个缺失的正整数
    free(vis);
    return n + 1;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missingNumber(arr, n));
    return 0;
}

3. Java

import java.util.Arrays;

class DSA {

    static int missingNumber(int[] arr) {
        int n = arr.length;

        // 用于标记元素是否出现过
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {

            // 如果元素在 1 到 n 的范围内
            // 就将其标记为已访问
            if (arr[i] > 0 && arr[i] <= n)
                vis[arr[i] - 1] = true;
        }

        // 查找原始数组中第一个未被访问的元素
        for (int i = 1; i <= n; i++) {
            if (!vis[i - 1]) {
                return i;
            }
        }

        // 如果 1 到 n 的所有元素都已访问
        // 那么 n+1 就是第一个缺失的正整数
        return n + 1;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

4. Python

def missingNumber(arr):
    n = len(arr)

    # 用于标记元素是否出现过
    vis = [False] * n
    for i in range(n):

        # 如果元素在 1 到 n 的范围内
        # 就将其标记为已访问
        if 0 < arr[i] <= n:
            vis[arr[i] - 1] = True

    # 查找原始数组中第一个未被访问的元素
    for i in range(1, n + 1):
        if not vis[i - 1]:
            return i

    # 如果 1 到 n 的所有元素都已访问
    # 那么 n+1 就是第一个缺失的正整数
    return n + 1

if __name__ == "__main__":
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

5. C#

using System;

class DSA {
    static int missingNumber(int[] arr) {
        int n = arr.Length;

        // 用于标记元素是否出现过
        bool[] vis = new bool[n];
        for (int i = 0; i < n; i++) {

            // 如果元素在 1 到 n 的范围内
            // 就将其标记为已访问
            if (arr[i] > 0 && arr[i] <= n)
                vis[arr[i] - 1] = true;
        }

        // 查找原始数组中第一个未被访问的元素
        for (int i = 1; i <= n; i++) {
            if (!vis[i - 1]) {
                return i;
            }
        }

        // 如果 1 到 n 的所有元素都已访问
        // 那么 n+1 就是第一个缺失的正整数
        return n + 1;
    }

    static void Main() {
        int[] arr = { 2, -3, 4, 1, 1, 7 };
        Console.WriteLine(missingNumber(arr));
    }
}

6. JavaScript

function missingNumber(arr) {
    let n = arr.length;

    // 用于标记元素是否出现过
    let vis = new Array(n).fill(false);
    for (let i = 0; i < n; i++) {

        // 如果元素在 1 到 n 的范围内
        // 就将其标记为已访问
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = true;
    }

    // 查找原始数组中第一个未被访问的元素
    for (let i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            return i;
        }
    }

    // 如果 1 到 n 的所有元素都已访问
    // 那么 n+1 就是第一个缺失的正整数
    return n + 1;
}

const arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

(三) 代码输出和算法复杂度

输出：

3

时间复杂度：O(n)

空间复杂度：O(n)

四、【最优解法】使用循环排序 —— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

该方法与循环排序的思想类似，将数组中的每个元素根据其值移动到正确的位置。对于每个数值 x（满足 1 ≤ x ≤ n），将其放到下标为 x - 1 的位置上。

最后，遍历数组，检查每个位置上的数字是否与预期一致。第一个数字与下标不匹配的位置，就是我们要找的最小缺失正整数。如果 1 到 n 的所有数字都在正确的位置上，那么下一个数字 n + 1 就是答案。

(二) 使用6种语言实现

1. C++

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int> &arr) {
    int n = arr.size();

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

        // 如果 arr[i] 在 [1, n] 范围内，且没有放在 (arr[i]-1) 下标处
        while (arr[i] >= 1 && arr[i] <= n
            && arr[i] != arr[arr[i] - 1]) {

            // 交换 arr[i] 和 arr[arr[i]-1]
            // 将 arr[i] 放到它对应的正确位置
            swap(arr[i], arr[arr[i] - 1]);
        }
    }

    // 如果某个数字不在对应的位置上
    // 它就是缺失的数字
    for (int i = 1; i <= n; i++) {
        if (i != arr[i-1]) {
            return i;
        }
    }

    // 如果 1 到 n 的所有数字都存在
    // 那么 n + 1 就是最小的缺失正整数
    return n + 1;
}

int main() {

    vector<int> arr = {2, -3, 4, 1, 1, 7};
    cout << missingNumber(arr);
    return 0;
}

2. C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int missingNumber(int arr[], int n) {

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

        // 如果 arr[i] 在 [1, n] 范围内，且没有放在 (arr[i]-1) 下标处
        while (arr[i] >= 1 && arr[i] <= n 
               && arr[i] != arr[arr[i] - 1]) {

            // 交换 arr[i] 和 arr[arr[i]-1]
            // 将 arr[i] 放到它对应的正确位置
            swap(&arr[i], &arr[arr[i] - 1]);
        }
    }

    // 如果某个数字不在对应的位置上
    // 它就是缺失的数字
    for (int i = 1; i <= n; i++) {
        if (i != arr[i-1]) {
            return i;
        }
    }

    // 如果 1 到 n 的所有数字都存在
    // 那么 n + 1 就是最小的缺失正整数
    return n + 1;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missingNumber(arr, n));
    return 0;
}

3. Java

import java.util.*;

class DSA {

    static int missingNumber(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {

            // 如果 arr[i] 在 [1, n] 范围内，且没有放在 (arr[i]-1) 下标处
            while (arr[i] >= 1 && arr[i] <= n
                   && arr[i] != arr[arr[i] - 1]) {

                // 交换 arr[i] 和 arr[arr[i]-1]
                // 将 arr[i] 放到它对应的正确位置
                int temp = arr[i];
                arr[i] = arr[arr[i] - 1];
                arr[temp - 1] = temp;
            }
        }

        // 如果某个数字不在对应的位置上
        // 它就是缺失的数字
        for (int i = 1; i <= n; i++) {
            if (i != arr[i - 1]) {
                return i;
            }
        }

        // 如果 1 到 n 的所有数字都存在
        // 那么 n + 1 就是最小的缺失正整数
        return n + 1;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

4. Pyton

def missingNumber(arr):

    n = len(arr)
    for i in range(n):

        # 如果 arr[i] 在 1 到 n 的范围内
        # 且没有放在 (arr[i]-1) 下标处
        while 1 <= arr[i] <= n and arr[i] != arr[arr[i] - 1]:

            # 交换 arr[i] 和 arr[arr[i]-1]
            # 将 arr[i] 放到它对应的正确位置
            temp = arr[i]
            arr[i] = arr[arr[i] - 1]
            arr[temp - 1] = temp

    # 如果某个数字不在对应的位置上
    # 它就是缺失的数字
    for i in range(1, n + 1):
        if i != arr[i - 1]:
            return i

    # 如果 1 到 n 的所有数字都存在
    # 那么 n + 1 就是最小的缺失正整数
    return n + 1

if __name__ == '__main__':
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

5. C#

using System;

class GfG {

    static int missingNumber(int[] arr) {

        int n = arr.Length;
        for (int i = 0; i < n; i++) {

            // 如果 arr[i] 在 1 到 n 的范围内
            // 且没有放在 (arr[i]-1) 下标处
            while (arr[i] >= 1 && arr[i] <= n
                   && arr[i] != arr[arr[i] - 1]) {

                // 交换 arr[i] 和 arr[arr[i]-1]
                // 将 arr[i] 放到它对应的正确位置
                int temp = arr[i];
                arr[i] = arr[arr[i] - 1];
                arr[temp - 1] = temp;
            }
        }

        // 如果某个数字不在对应的位置上
        // 它就是缺失的数字
        for (int i = 1; i <= n; i++) {
            if (i != arr[i - 1]) {
                return i;
            }
        }

        // 如果 1 到 n 的所有数字都存在
        // 那么 n + 1 就是最小的缺失正整数
        return n + 1;
    }

    static void Main() {
        int[] arr = { 2, -3, 4, 1, 1, 7 };
        Console.WriteLine(missingNumber(arr));
    }
}

6. JavaScript

function missingNumber(arr) {

  let n = arr.length;
  for (let i = 0; i < n; i++) {

    // 如果 arr[i] 在 1 到 n 的范围内
    // 且没有放在 (arr[i]-1) 下标处
    while (arr[i] >= 1 && arr[i] <= n 
           && arr[i] !== arr[arr[i] - 1]) {

      // 交换 arr[i] 和 arr[arr[i]-1]
      // 将 arr[i] 放到它对应的正确位置
      let temp = arr[i];
      arr[i] = arr[arr[i] - 1];
      arr[temp - 1] = temp;
    }
  }

  // 如果某个数字不在对应的位置上
  // 它就是缺失的数字
  for (let i = 1; i <= n; i++) {
    if (i !== arr[i - 1]) {
      return i;
    }
  }

  // 如果 1 到 n 的所有数字都存在
  // 那么 n + 1 就是最小的缺失正整数
  return n + 1;
}

let arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

(三) 代码输出和算法复杂度

输出：

3

时间复杂度：O(n)

空间复杂度：O(1)

五、【替代解法-1】通过取反数组元素 —— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

首先将所有正整数移动到数组的左侧。然后，对于左侧的有效区间，通过将下标为 val - 1 的元素取反，来标记数值 val（满足 1 ≤ val ≤ k）已经出现过。这种标记方式能帮我们确定哪些数字是存在的。最后，遍历标记后的区间，找到第一个仍为正数的下标，这个位置就代表最小的缺失正整数。如果所有位置都被标记（取反），那么缺失的数字就是 k + 1。

(二) 使用6种语言实现

1. C++

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int> &arr) {
    int pivotIdx = 0;
    int n = arr.size();

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

        // 将正数移动到数组左侧
        if (arr[i] > 0) {
            swap(arr[i], arr[pivotIdx]);
            pivotIdx++;
        }
    }

    // 返回第一个非正数的下标
    return pivotIdx;
}

int missingNumber(vector<int> &arr) {
    int k = partition(arr);

    // 遍历数组的正数部分
    for (int i = 0; i < k; i++) {

        // 取绝对值获取原始数值
        int val = abs(arr[i]);

        // 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];

        }
    }

    // 查找第一个未被标记的正数下标
    for (int i = 0; i < k; i++) {

        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // 如果 1 到 k 的所有数字都已标记
    // 那么缺失的数字就是 k + 1
    return k + 1;
}

int main() {

    vector<int> arr = {2, -3, 4, 1, 1, 7};
    cout << missingNumber(arr);
    return 0;
}

2. C

#include <stdio.h>

int partition(int *arr, int n) {
    int pivotIdx = 0;

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

        // 将正数移动到数组左侧
        if (arr[i] > 0) {
            int temp = arr[i];
            arr[i] = arr[pivotIdx];
            arr[pivotIdx] = temp;
            pivotIdx++;
        }
    }

    // 返回第一个非正数的下标
    return pivotIdx;
}

int missingNumber(int *arr, int n) {
    int k = partition(arr, n);

    // 遍历数组的正数部分
    for (int i = 0; i < k; i++) {

        // 取绝对值获取原始数值
        int val = abs(arr[i]);

        // 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];
        }
    }

    // 查找第一个未被标记的正数下标
    for (int i = 0; i < k; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // 如果 1 到 k 的所有数字都已标记
    // 那么缺失的数字就是 k + 1
    return k + 1;
}

int main() {

    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missingNumber(arr, n));
    return 0;
}

3. Java

import java.util.Arrays;

class DSA {

    static int partition(int[] arr) {
        int pivotIdx = 0;
        int n = arr.length;

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

            // 将正数移动到数组左侧
            if (arr[i] > 0) {
                int temp = arr[i];
                arr[i] = arr[pivotIdx];
                arr[pivotIdx] = temp;
                pivotIdx++;
            }
        }

        // 返回第一个非正数的下标
        return pivotIdx;
    }

    static int missingNumber(int[] arr) {
        int k = partition(arr);

        // 遍历数组的正数部分
        for (int i = 0; i < k; i++) {

            // 取绝对值获取原始数值
            int val = Math.abs(arr[i]);

            // 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
            if (val - 1 < k && arr[val - 1] > 0) {
                arr[val - 1] = -arr[val - 1];
            }
        }

        // 查找第一个未被标记的正数下标
        for (int i = 0; i < k; i++) {
            if (arr[i] > 0) {
                return i + 1;
            }
        }

        // 如果 1 到 k 的所有数字都已标记
        // 那么缺失的数字就是 k + 1
        return k + 1;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

4. Python

def partition(arr):
    pivotIdx = 0
    n = len(arr)

    for i in range(n):

        # 将正数移动到数组左侧
        if arr[i] > 0:
            arr[i], arr[pivotIdx] = arr[pivotIdx], arr[i]
            pivotIdx += 1

    # 返回第一个非正数的下标
    return pivotIdx

def missingNumber(arr):
    k = partition(arr)

    # 遍历数组的正数部分
    for i in range(k):

        # 取绝对值获取原始数值
        val = abs(arr[i])

        # 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
        if val - 1 < k and arr[val - 1] > 0:
            arr[val - 1] = -arr[val - 1]

    # 查找第一个未被标记的正数下标
    for i in range(k):
        if arr[i] > 0:
            return i + 1

    # 如果 1 到 k 的所有数字都已标记
    # 那么缺失的数字就是 k + 1
    return k + 1

if __name__ == "__main__":
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

5. C#

using System;

class DSA {

    static int Partition(int[] arr) {
        int pivotIdx = 0;
        int n = arr.Length;

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

            // 将正数移动到数组左侧
            if (arr[i] > 0) {
                int temp = arr[i];
                arr[i] = arr[pivotIdx];
                arr[pivotIdx] = temp;
                pivotIdx++;
            }
        }

        // 返回第一个非正数的下标
        return pivotIdx;
    }

    static int missingNumber(int[] arr) {

        int k = Partition(arr);

        // 遍历数组的正数部分
        for (int i = 0; i < k; i++) {

            // 取绝对值获取原始数值
            int val = Math.Abs(arr[i]);

            // 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
            if (val - 1 < k && arr[val - 1] > 0)
                arr[val - 1] = -arr[val - 1];
        }

        // 查找第一个未被标记的正数下标
        for (int i = 0; i < k; i++) {
            if (arr[i] > 0) {
                return i + 1;
            }
        }

        // 如果 1 到 k 的所有数字都已标记
        // 那么缺失的数字就是 k + 1
        return k + 1;
    }

    static void Main() {
        int[] arr = { 2, -3, 4, 1, 1, 7 };
        Console.WriteLine(missingNumber(arr));
    }
}

6. JavaScript

function partition(arr) {
    let pivotIdx = 0;
    const n = arr.length;

    for (let i = 0; i < n; i++) {
        
        // 将正数移动到数组左侧
        if (arr[i] > 0) {
            [arr[i], arr[pivotIdx]] = [arr[pivotIdx], arr[i]];
            pivotIdx++;
        }
    }

    // 返回第一个非正数的下标
    return pivotIdx;
}

function missingNumber(arr) {
    const k = partition(arr);

    // 遍历数组的正数部分
    for (let i = 0; i < k; i++) {
        
        // 取绝对值获取原始数值
        const val = Math.abs(arr[i]);

        // 如果 val 在有效范围内，将下标 val-1 处的元素标记为负数
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];
        }
    }

    // 查找第一个未被标记的正数下标
    for (let i = 0; i < k; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // 如果 1 到 k 的所有数字都已标记
    // 那么缺失的数字就是 k + 1
    return k + 1;
}

// 测试代码
const arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

(三) 代码输出和算法复杂度

输出：

3

时间复杂度：O(n)

空间复杂度：O(1)

六、【替代解法-2】通过标记索引 —— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

首先检查数组中是否包含数字 1，如果不包含，答案就是 1。如果包含，就将所有超出范围 [1, n] 的数字替换为 1。接着再次遍历数组，通过在下标 x-1 处加上 n 的方式，标记每个数字 x 已经出现。最后再次遍历数组，查找第一个未被标记的下标，该位置对应的就是缺失的数字。

(二) 使用6种语言实现

1. C++

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int> &arr) {
  
  	int n = arr.size();
    bool flag = false;

    // 检查数组中是否包含数字 1
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            flag = true;
            break;
        }
    }

    // 如果不存在 1，直接返回 1
    if (flag == false)
        return 1;

    // 将所有超出范围的数替换为 1
    for (int i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
        
    }

    // 在数组内直接标记数字出现过
  	for (int i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // 查找第一个值小于等于 n 的下标
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n)
            return i + 1;
    }

    // 如果数组包含 1 到 n 的所有数字
    return n + 1;
}

int main() {
    vector<int> arr = {2, -3, 4, 1, 1, 7};
  
    cout << missingNumber(arr);
	return 0;
}

2. C

#include <stdio.h>

int missingNumber(int arr[], int n) {
    int flag = 0;

    // 检查数组中是否包含数字 1
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            flag = 1;
            break;
        }
    }

    // 如果不存在 1，直接返回 1
    if (flag == 0)
        return 1;

    // 将所有超出范围的数替换为 1
    for (int i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
    }

    // 在数组内直接标记数字出现过
    for (int i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // 查找第一个值小于等于 n 的下标
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n)
            return i + 1;
    }

    // 如果数组包含 1 到 n 的所有数字
    return n + 1;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("%d", missingNumber(arr, n));
    return 0;
}

3. Java

import java.util.*;
class DSA {

    static int missingNumber(int[] arr) {
        int n = arr.length;
        boolean flag = false;

        // 检查数组中是否包含数字 1
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                flag = true;
                break;
            }
        }

        // 如果不存在 1，直接返回 1
        if (!flag)
            return 1;

        // 将所有超出范围的数替换为 1
        for (int i = 0; i < n; i++) {
            if (arr[i] <= 0 || arr[i] > n)
                arr[i] = 1;
        }

        // 在数组内直接标记数字出现过
        for (int i = 0; i < n; i++) {
            arr[(arr[i] - 1) % n] += n;
        }

        // 查找第一个值小于等于 n 的下标
        for (int i = 0; i < n; i++) {
            if (arr[i] <= n)
                return i + 1;
        }

        // 如果数组包含 1 到 n 的所有数字
        return n + 1;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

4. Python

def missingNumber(arr):
    n = len(arr)
    flag = False

    # 检查数组中是否包含数字 1
    for i in range(n):
        if arr[i] == 1:
            flag = True
            break

    # 如果不存在 1，直接返回 1
    if not flag:
        return 1

    # 将所有超出范围的数替换为 1
    for i in range(n):
        if arr[i] <= 0 or arr[i] > n:
            arr[i] = 1

    # 在数组内直接标记数字出现过
    for i in range(n):
        arr[(arr[i] - 1) % n] += n

    # 查找第一个值小于等于 n 的下标
    for i in range(n):
        if arr[i] <= n:
            return i + 1

    # 如果数组包含 1 到 n 的所有数字
    return n + 1

if __name__ == "__main__":
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

5. C#

using System;

class DFA {

    static int missingNumber(int[] arr) {
        int n = arr.Length;
        bool flag = false;

        // 检查数组中是否包含数字 1
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                flag = true;
                break;
            }
        }

        // 如果不存在 1，直接返回 1
        if (!flag)
            return 1;

        // 将所有超出范围的数替换为 1
        for (int i = 0; i < n; i++) {
            if (arr[i] <= 0 || arr[i] > n)
                arr[i] = 1;
        }

        // 在数组内直接标记数字出现过
        for (int i = 0; i < n; i++) {
            arr[(arr[i] - 1) % n] += n;
        }

        // 查找第一个值小于等于 n 的下标
        for (int i = 0; i < n; i++) {
            if (arr[i] <= n)
                return i + 1;
        }

        // 如果数组包含 1 到 n 的所有数字
        return n + 1;
    }

    static void Main() {
        int[] arr = {2, -3, 4, 1, 1, 7};
        Console.WriteLine(missingNumber(arr));
    }
}

6. JavaScript

function missingNumber(arr) {
  let n = arr.length;
  let flag = false;

  // 检查数组中是否包含数字 1
  for (let i = 0; i < n; i++) {
    if (arr[i] === 1) {
      flag = true;
      break;
    }
  }

  // 如果不存在 1，直接返回 1
  if (!flag) return 1;

  // 将所有超出范围的数替换为 1
  for (let i = 0; i < n; i++) {
    if (arr[i] <= 0 || arr[i] > n) arr[i] = 1;
  }

  // 在数组内直接标记数字出现过
  for (let i = 0; i < n; i++) {
    arr[(arr[i] - 1) % n] += n;
  }

  // 查找第一个值小于等于 n 的下标
  for (let i = 0; i < n; i++) {
    if (arr[i] <= n) return i + 1;
  }

  // 如果数组包含 1 到 n 的所有数字
  return n + 1;
}

let arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

(三) 代码输出和算法复杂度

输出：

3

时间复杂度：O(n)

空间复杂度：O(1)

# 算法 # 面试 # 职场和发展
Logo
乐奇 Rokid 开放社区

更多推荐

Word Embedding ：从分布式假设到神经网络语言模型

Word Embedding（词嵌入）是一种将离散的词汇符号映射到连续的低维稠密向量空间的技术。在这个向量空间中，语义相似的词在几何距离上彼此接近，从而实现了从"符号匹配"到"语义计算"的跨越。核心定义词嵌入是将单词（或多词短语）表示为固定维度的实值向量，这些向量之间的距离（例如余弦相似度）反映了单词之间的相关性，这种相关性基于单词通常出现的上下文。分布式假设（1954）↓统计共现分析（LSA/S

avatar 乐奇 Rokid 开放社区

3 分钟装好 foobox 皮肤：foobar2000 界面升级安装教程

foobox 是一个 foobar2000 的 DUI 皮肤配置，装好后默认界面就变成带亮、暗两套主题的多面板播放器。它适合已经用 foobar2000、只想换界面不想改播放习惯的 Windows 用户：皮肤只动外观，不碰播放器核心。## 先看适不适合你- 你在 Windows 10 1607 或更高版本上用 foobar2000，想要更顺眼的界面；- 你的曲库不小，想要分组管理和搜索；

avatar 乐奇 Rokid 开放社区

镜游小导：运行在 Rokid AR 眼镜上的景区实景讲解智能体

项目以 RokidAIUI 开放智能体形态交付：页面用.ink描述，运行在眼镜端智能体运行时，直接调用系统能力。AGENTS.md身份镜游小导v1.0.0，景区 AR 实景讲解智能体；权限（Capabilities）microphonenetworkaudiogyroscope；技能（Skills）。

avatar 乐奇 Rokid 开放社区