友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
268. Missing Number
这道题跟 41. First Missing Positive 很像！
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
思路分析
-
一刷
-
二刷
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
31
32
33
34
35
36
37
38
39
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Number.
*
* Memory Usage: 38.9 MB, less than 100.00% of Java online submissions for Missing Number.
*
* Copy from: https://leetcode.com/problems/missing-number/solution/[Missing Number solution - LeetCode]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-05 21:30
*/
public int missingNumber(int[] nums) {
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
int expectSum = nums.length * (nums.length + 1) / 2;
return expectSum - actualSum;
}
/**
* Runtime: 7 ms, faster than 24.02% of Java online submissions for Missing Number.
*
* Memory Usage: 39.8 MB, less than 100.00% of Java online submissions for Missing Number.
*/
public int missingNumberSort(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
}
}
if (nums[nums.length - 1] == nums.length - 1) {
return nums.length;
}
return -1;
}
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
/**
* 循环排序的解法
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-29 19:07:11
*/
public int missingNumber(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] != i && nums[i] < n) {
swap(nums, nums[i], i--);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}
return n;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}