用原地交换变量,分组异或 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

动态规划,求解《801. 使序列递增的最小交换次数》
动态规划,求解《801. 使序列递增的最小交换次数》
定长列表存储索引,自定义排序,双指针求解《870. 优势洗牌》
定长列表存储索引,自定义排序,双指针求解《870. 优势洗牌》
顺序遍历,动态规划(单变量空间压缩),求解《1800. 最大升序子数组和》
顺序遍历,动态规划(单变量空间压缩),2 种思想,归于 1 种解法,求解《1800. 最大升序子数组和》