用原地交换变量，分组异或 2 种算法，用 append / push_back / Array.Resize(ref array, new size) / realloc 扩容固定列表，用 x & -x 寻找最右边的 1 位运算，在 O(n) 时间复杂度和 O(1) 空间复杂度，2 解法求解《面试题 17.19. 消失的两个数字》
例题
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000
答案
空间复杂度增加说明： 使用 2 个长度的同构数组作为结构数组，是为了避免在返回时重新构造数组
原地交换变量
var missingTwo = function(nums) {
const n = nums.length, r = new Uint16Array(2)
nums[n] = 0
nums[n + 1] = 0
for (let i = 0; i < n + 2; i++) {
while (nums[i] !== 0 && i !== nums[i] - 1) swap(nums, i, nums[i] - 1)
}
for (let i = 0, j = 0; i < n + 2; i++) {
if (nums[i] === 0) r[j++] = i + 1
}
return r
};
const swap = (nums, a, b) => {
nums[b] = nums[a] + nums[b] - (nums[a] = nums[b])
}function missingTwo(nums: number[]): number[] {
const n = nums.length, r = new Array(2)
nums[n] = 0
nums[n + 1] = 0
for (let i = 0; i < n + 2; i++) {
while (nums[i] !== 0 && i !== nums[i] - 1) swap(nums, i, nums[i] - 1)
}
for (let i = 0, pos = 0; i < n + 2; i++) {
if (nums[i] === 0) r[pos++] = i + 1
}
return r
};
function swap(nums: number[], a: number, b: number) {
nums[a] ^= nums[b]
nums[b] ^= nums[a]
nums[a] ^= nums[b]
}class Solution {
function missingTwo($nums) {
$n = count($nums);
$r = array_fill(0, 2, 0);
$nums[$n] = 0;
$nums[$n + 1] = 0;
for ($i = 0; $i < $n + 2; $i++) {
while ($nums[$i] !== 0 && $i !== $nums[$i] - 1) $this->swap($nums, $i, $nums[$i] - 1);
}
for ($i = 0, $j = 0; $i < $n + 2; $i++) if ($nums[$i] === 0) $r[$j++] = $i + 1;
return $r;
}
function swap(&$nums, $a, $b) {
list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
}
}func missingTwo(nums []int) []int {
n, r := len(nums), make([]int, 2)
nums = append(nums, 0, 0)
nums[n], nums[n + 1] = 0, 0
for i := 0; i < n + 2; i++ {
for nums[i] != 0 && i != nums[i] - 1 {
swap(nums, i, nums[i] - 1)
}
}
for i, j := 0, 0; i < n + 2; i++ {
if nums[i] == 0 {
r[j] = i + 1
j++
}
}
return r
}
func swap(nums []int, a, b int) {
nums[a], nums[b] = nums[b], nums[a]
}void swap(int* pa, int* pb) {
int t = *pa;
*pa = *pb;
*pb = t;
}
int* missingTwo(int* nums, int numsSize, int* returnSize){
nums = realloc(nums, sizeof(int) * (numsSize + 2));
nums[numsSize] = 0;
nums[numsSize + 1] = 0;
for (int i = 0; i < numsSize + 2; i++) {
while (nums[i] != 0 && i != nums[i] - 1) swap(&nums[i], &nums[nums[i] - 1]);
}
int* r = malloc(sizeof(int) * 2);
for (int i = 0, j = 0; i < numsSize + 2; i++) {
if (nums[i] == 0) r[j++] = i + 1;
}
*returnSize = 2;
return r;
}public class Solution {
public int[] MissingTwo(int[] nums) {
int n = nums.Length;
Array.Resize(ref nums, n + 2);
for (int i = 0; i < n + 2; i++) {
while (nums[i] != 0 && i != nums[i] - 1) swap(nums, i, nums[i] - 1);
}
int[] r = new int[2];
for (int i = 0, j = 0; i < n + 2; i++) {
if (nums[i] == 0) r[j++] = i + 1;
}
return r;
}
public void swap(int[] nums, int a, int b) {
nums[b] = nums[a] + nums[b] - (nums[a] = nums[b]);
}
}class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int n = nums.size();
nums.push_back(0);
nums.push_back(0);
vector<int> r(2);
for (int i = 0; i < n + 2; i++) {
while (nums[i] != 0 && i != nums[i] - 1) swap(nums[i], nums[nums[i] - 1]);
}
for (int i = 0, j = 0; i < n + 2; i++) {
if (nums[i] == 0) r[j++] = i + 1;
}
return r;
}
};class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
n, r = len(nums), []
nums.append(0)
nums.append(0)
for i in range(0, n + 2):
while nums[i] != 0 and i != nums[i] - 1: self.swap(nums, i, nums[i] - 1)
for i in range(0, n + 2):
if nums[i] == 0: r.append(i + 1)
return r
def swap(self, nums: List[int], a: int, b: int):
nums[a], nums[b] = nums[b], nums[a]分组异或 · 位运算
var missingTwo = function(nums) {
const n = nums.length
let xor = 0
for (let i = 0; i < n; i++) xor ^= nums[i] ^ i + 1
xor ^= n + 1 ^ n + 2
const rightest1 = xor & -xor, r = new Uint16Array(2)
for (let i = 0; i < n; i++) r[nums[i] & rightest1 && 1] ^= nums[i]
for (let i = 1; i <= n + 2; i++) r[i & rightest1 && 1] ^= i
return r
};function missingTwo(nums: number[]): number[] {
const n = nums.length
let xor = 0
for (let i = 0; i < n; i++) xor ^= nums[i] ^ i + 1
xor ^= n + 1 ^ n + 2
const rightest1 = xor & -xor, r = new Array(2)
for (let i = 0; i < n + 2; i++) {
if (i < n) r[nums[i] & rightest1 && 1] ^= nums[i]
r[i + 1 & rightest1 && 1] ^= i + 1
}
return r
};class Solution {
function missingTwo($nums) {
$n = count($nums);
for ($i = 0; $i < $n; $i++) $xor ^= $nums[$i] ^ ($i + 1);
$xor ^= $n + 1 ^ $n + 2;
$rightest1 = $xor & -$xor;
$r = array_fill(0, 2, 0);
foreach ($nums as $num) $r[$num & $rightest1 ? 1 : 0] ^= $num;
for ($i = 1; $i <= $n + 2; $i++) $r[$i & $rightest1 ? 1 : 0] ^= $i;
return $r;
}
}class Solution {
function missingTwo($nums) {
$n = count($nums);
for ($i = 0; $i < $n; $i++) $xor ^= $nums[$i] ^ ($i + 1);
$xor ^= $n + 1 ^ $n + 2;
$rightest1 = $xor & -$xor;
$r = array_fill(0, 2, 0);
for ($i = 0; $i < $n + 2; $i++) {
if ($i < $n) $r[$nums[$i] & $rightest1 ? 1 : 0] ^= $nums[$i];
$r[$i + 1 & $rightest1 ? 1 : 0] ^= $i + 1;
}
return $r;
}
}func missingTwo(nums []int) []int {
n, xor := len(nums), 0
for i := 0; i < n; i++ {
xor ^= nums[i] ^ (i + 1)
}
xor ^= (n + 1) ^ (n + 2)
rightest1, r := xor & - xor, make([]int, 2)
for i := 0; i < n; i++ {
if nums[i] & rightest1 > 0 {
r[1] ^= nums[i]
} else {
r[0] ^= nums[i]
}
}
for i := 1; i <= n + 2; i++ {
if i & rightest1 > 0 {
r[1] ^= i
} else {
r[0] ^= i
}
}
return r
}class Solution {
public int[] missingTwo(int[] nums) {
int n = nums.length, xor = 0;
for (int i = 0; i < n; i++) xor ^= nums[i] ^ i + 1;
xor ^= n + 1 ^ n + 2;
int rightest1 = xor & -xor;
int[] r = new int[2];
for (int i = 0; i < n; i++) r[(nums[i] & rightest1) > 0 ? 1 : 0] ^= nums[i];
for (int i = 1; i <= n + 2; i++) r[(i & rightest1) > 0 ? 1 : 0] ^= i;
return r;
}
}public class Solution {
public int[] MissingTwo(int[] nums) {
int n = nums.Length, xor = 0;
for (int i = 0; i < n; i++) xor ^= nums[i] ^ i + 1;
xor ^= n + 1 ^ n + 2;
int rightest = xor & -xor;
int[] r = new int[2];
for(int i = 0; i < n; i++) r[(nums[i] & rightest) > 0 ? 1 : 0] ^= nums[i];
for(int i = 1; i <= n + 2; i++) r[(i & rightest) > 0 ? 1 : 0] ^= i;
return r;
}
}int* missingTwo(int* nums, int numsSize, int* returnSize){
int xor = 0;
for (int i = 0; i < numsSize; i++) xor ^= nums[i] ^ i + 1;
xor ^= numsSize + 1 ^ numsSize + 2;
int rightest1 = xor & -xor;
int* r = malloc(sizeof(int) * 2);
memset(r, 0, sizeof(int) * 2);
for (int i = 0; i < numsSize; i++) r[nums[i] & rightest1 && 1] ^= nums[i];
for (int i = 1; i <= numsSize + 2; i++) r[i & rightest1 && 1] ^= i;
*returnSize = 2;
return r;
}class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; i++) sum ^= nums[i] ^ i + 1;
sum ^= n + 1 ^ n + 2;
int rightest1 = sum & -sum;
vector<int> r(2);
for (int i = 0; i < n; i++) r[nums[i] & rightest1 && 1] ^= nums[i];
for (int i = 1; i <= n + 2; i++) r[i & rightest1 && 1] ^= i;
return r;
}
};class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
n, xor = len(nums), 0
for i, num in enumerate(nums): xor ^= num ^ i + 1
xor ^= n + 1 ^ n + 2
rightest, r = xor & -xor, [0] * 2
for num in nums: r[num & rightest and 1] ^= num
for i in range(1, n + 3): r[i & rightest and 1] ^= i
return r