丢失的数字
难度:
标签:
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
代码结果
运行时间: 27 ms, 内存: 16.9 MB
/*
* 思路：
* 使用 Java Stream API 计算数组的总和，然后减去高斯求和公式得到的总和，
* 得到缺失的数字。
*/
import java.util.Arrays;
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int totalSum = n * (n + 1) / 2;
int sum = Arrays.stream(nums).sum();
return totalSum - sum;
}
}解释
方法:
此题解采用了和的差值法。首先计算出0到n的和s，然后遍历数组nums，将数组中每个元素的值从s中减去。最后，s中剩余的值就是缺失的数字。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么采用和的差值法来解决这个问题，而不是使用其它数据结构如哈希表或位运算？
▷🦆
在和的差值法中，如何确保不会因为整数溢出而得到错误的结果？
▷🦆
如果输入的数组nums中包含重复的数字，这种方法还会有效吗？
▷🦆
这种方法能否处理所有元素都正常出现，但数组长度比预期短一位的情况（即缺失的是最大的数字n）？
▷相关问题
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1] 输出：1
示例 2 ：
输入：nums = [4,1,2,1,2] 输出：4
示例 3 ：
输入：nums = [1] 输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2] 输出：2
示例 2：
输入：nums = [3,1,3,4,2] 输出：3
示例 3 :
输入：nums = [3,3,3,3,3] 输出：3
提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
情侣牵手
n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。
示例 1:
输入: row = [0,2,1,3] 输出: 1 解释: 只需要交换row[1]和row[2]的位置即可。
示例 2:
输入: row = [3,2,0,1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
提示:
2n == row.length2 <= n <= 30n是偶数0 <= row[i] < 2nrow中所有元素均无重复