每日一题-20240118

发表于 更新于 分类于 阅读次数： 本文字数： 408 阅读时长 ≈ 1 分钟

题目描述

面试题 17.04. 消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

注意：本题相对书上原题稍作改动

示例 1：

1
2
输入：[3,0,1]
输出：2

示例 2：

1
2
输入：[9,6,4,2,3,5,7,0,1]
输出：8

解题思路

方法一：排序后与数组索引比较

  1. 将数组按照从小到大的顺序排序。
  2. 遍历排序后的数组，若当前元素值不等于索引，则索引值为缺失的整数。
  3. 若遍历结束仍未返回，则缺失的数为数组长度 + 1。

方法二：数学

利用等差数列求和公式：和=（首项+末项）×项数÷2。

  1. 利用求和公式求不缺失数字数组的和为sum。
  2. 对输入数组求和为total。
  3. 缺失的数为：sum - total。

代码实现

源码

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution1704 {
  public static int missingNumber(int[] nums) {
        sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length + 1;
    }

    /**
     * 排序
     *
     * @param arr
     * @author Forest Dong
     * @date 2024/01/21 16:41
     */
    private static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution1704 {
    /**
     * 思路：根据高斯求和公式：(首项 + 尾项) * (项数) / 2
     *
     * @param nums
     * @return int
     * @author Forest Dong
     * @date 2024/01/21 17:40
     */
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = (n * (n + 1)) / 2;
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        return sum - total;
    }

		public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.err.println(missingNumber(nums));
    }
}