Java消失的数字

ops/2024/10/18 9:22:44/

题目要求

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8

力扣原题
https://leetcode.cn/problems/missing-number-lcci/description/

实现代码

java">public class Main {public static int missingNumber(int[] nums) {// 法一: 定义一个不缺失整数的新数组。把 缺失数组的每个元素的值 当作 新数组的对应下标，让该下标对应的值+1。新数组元素为0的下标就是缺失的数字int[] array = new int[nums.length + 1];for (int num : nums) {array[num]++;}int tmp = 0;for (int i = 0; i < array.length; i++) {if (array[i] == 0) {tmp = i;}}return tmp;}public static void main(String[] args) {int[] array = {9, 6, 4, 2, 3, 5, 7, 0, 1};System.out.println(missingNumber(array));}
}

java">public class Main {public static int missingNumber(int[] nums) {// 法二： 利用异或的自反性：a^b^b = a^0 = a。// 用0开始遍历缺失整数数组和不缺失整数数组，两个数组相同的元素都异或为0，最后0和缺失的数字异或得出缺失的数字// 格式一int n = 0;for (int i = 0; i < nums.length; i++) {n ^= i;n ^= nums[i];}// 因为 少异或一次不缺失整数数组的最后一个元素return n ^ nums.length;/*        // 格式二int n = 0;// 不缺失整数数组for (int i = 0; i <= nums.length; i++) {n ^= i;}// 缺失整数数组for (int i = 0; i < nums.length; i++) {n ^= nums[i];}return n;*/}public static void main(String[] args) {int[] array = {9, 6, 4, 2, 3, 5, 7, 0, 1};System.out.println(missingNumber(array));}
}

java">public class Main {public static int missingNumber(int[] nums) {// 法三: 用高斯求和公式( 等差数列求和公式：(n*(n+1))/2[n表示数列中的最后一项] )求出[0, nums.length]的和。// 再用该和依次减去nums数组里的每个元素，得出缺失的数字// nums.length: 对应不缺失整数的数组的最大值(即数组升序最后一项)int sum = (nums.length * (nums.length + 1)) / 2;//想不到用高斯求和公式,普通累加到nums.length下标也可以for (int num : nums) {sum -= num;}return sum;}public static void main(String[] args) {int[] array = {9, 6, 4, 2, 3, 5, 7, 0, 1};System.out.println(missingNumber(array));}
}