Missing Number (E)
題目
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: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
題意
給定一個長度為n的陣列，從 0-n 這 n+1 個數中選取 n 個數填充入陣列中，找到缺失的那一個數，
思路
交換法：第一次遍歷陣列，將nums[i]與下標為nums[i]的數進行交換，第二次遍歷陣列，如果遇到 i != nums[i]，說明i就是缺失的數，
求和法：先求 0-n 的和，再求陣列中數的和，相減就是缺失的數，
異或法：根據相同的數異或為0的性質， 將陣列中所有數異或一遍，再將結果與 0-n 異或一遍，相同的數會互相抵消，得到的結果就是缺失的數，
代碼實作
Java
交換
class Solution {
public int missingNumber(int[] nums) {
int i = 0;
while (i < nums.length) {
if (nums[i] >= nums.length || nums[i] == i) {
i++;
} else {
swap(nums, i, nums[i]);
}
}
for (int j = 0; j < nums.length; j++) {
if (nums[j] != j) {
return j;
}
}
return nums.length;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
求和
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int sum1 = (len + 1) * len / 2;
int sum2 = 0;
for (int num : nums) {
sum2 += num;
}
return sum1 - sum2;
}
}
異或
class Solution {
public int missingNumber(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
res = res ^ nums[i] ^ (i + 1);
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/43508.html
標籤：其他