5 种方法交换变量,用绝对值和求模标记,用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法:求解《442. 数组中重复的数据》

2022-05-08 13:16:43

利用 5 种方法交换变量,用绝对值和求模标记,用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法求解《442. 数组中重复的数据》

交换变量的 5 种方法

中间变量法

t = a
a = b
b = t

解构赋值法

[a, b] = [b, a]
a, b = b, a
a, b = b, a
list($a, $b) = array($b, $a);

位运算法

a = a ^ b
b = a ^ b
a = a ^ b 

加减法

a = a + b
b = a - b
a = a - b

求和减赋值法

b = a + b - (a = b)

乘除法:a , b 中不能有 0

a = a * b
b = a / b
a = a / b

例题

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

答案

交换变量

var findDuplicates = function(nums) {
  const r = [], n = nums.length
  for (let i = 0; i < n; i++) {
    while (nums[i] && nums[i] !== i + 1) {
      if (nums[i] !== nums[nums[i] - 1]) swap(nums, i, nums[i] - 1)
      else {
        r.push(nums[i])
        nums[nums[i] - 1] = null
        break
      }
    }
  }
  return r
};
const swap = (nums, a, b) => {
  nums[a] += nums[b]
  nums[b] = nums[a] - nums[b]
  nums[a] -= nums[b]
}
func findDuplicates(nums []int) []int {
  r := []int{}
  for i, _ := range nums {
    for nums[i] > 0 && nums[i] != i + 1 {
      if nums[i] != nums[nums[i] - 1] {
        swap(nums, i, nums[i] - 1)
      } else {
        r = append(r, nums[i])
        nums[nums[i] - 1] = 0
        break
      }
    } 
  }
  return r
}
func swap(nums []int, a int, b int) {
  nums[a] ^= nums[b]
  nums[b] ^= nums[a]
  nums[a] ^= nums[b]
}
class Solution {
  function findDuplicates($nums) {
    $r = [];
    foreach($nums as $i => $_) {
      while ($nums[$i] > 0 && $nums[$i] !== $i + 1) {
        if ($nums[$i] !== $nums[$nums[$i] - 1]) {
          $this->swap($nums, $i, $nums[$i] - 1);
        } else {
          array_push($r, $nums[$i]);
          $nums[$nums[$i] - 1] = 0;
          break;
        }
      }
    }
    return $r;
  }
  function swap(&$nums, $a, $b) {
    $nums[$b] = $nums[$a] + $nums[$b] - ($nums[$a] = $nums[$b]);
  }
}

位图

var findDuplicates = function(nums) {
  const b = new Bit(), n = nums.length, r = []
  for (let i = 0; i < n; i++) {
    if (b.has(nums[i])) r.push(nums[i])
    else b.add(nums[i])
  }
  return r
};
class Bit {
  constructor() {
    this.bit = 0n
  }
  has(i) {
    return (this.bit & 1n << BigInt(i)) > 0n
  }
  add(i) {
    this.bit |= 1n << BigInt(i)
  }
}
var findDuplicates = function(nums) {
  let bit = 0n
  const n = nums.length, r = []
  for (let i = 0; i < n; i++) {
    const j = BigInt(nums[i])
    if (bit & 1n << j) r.push(nums[i])
    else bit |= 1n << j
  }
  return r
};

掩码
var findDuplicates = function(nums) {
  const n = nums.length, r = []
  let mask = (1n << BigInt(n + 1)) - 1n
  for (let i = 0; i < n; i++) {
    const j = BigInt(nums[i])
    if ((mask & 1n << j) === 0n) r.push(nums[i])
    else mask ^= 1n << j
  }
  return r
};
标记 · 绝对值

var findDuplicates = function(nums) {
  r = [], n = nums.length
  for (let i = 0; i < n; i++) {
    const j = Math.abs(nums[i]) - 1
    if (nums[j] > 0) nums[j] = -nums[j] 
    else r.push(j + 1)
  } 
  return r
};
func findDuplicates(nums []int) []int {
  r := []int{}
  for i, _ := range nums {
    j := int(math.Abs(float64(nums[i]))) - 1
    if nums[j] > 0 {
      nums[j] = -nums[j]
    } else {
      r = append(r, j + 1)
    }
  }
  return r
}
class Solution {
  function findDuplicates($nums) {
    $r = [];
    foreach ($nums as $i => $v) {
      $j = abs($v) - 1;
      if ($nums[$j] > 0) $nums[$j] = -$nums[$j];
      else $r []= $j + 1;
    }
    return $r;
  }
}

标记 · 取模

var findDuplicates = function(nums) {
  r = [], n = nums.length
  for (let i = 0; i < n; i++) {
    const j = (nums[i] - 1) % n
    if (nums[j] <= n) nums[j] += n
    else r.push(j + 1)
  } 
  return r
};
func findDuplicates(nums []int) []int {
  r, n := []int{}, len(nums)
  for i, _ := range nums {
    j := (nums[i] - 1) % n 
    if nums[j] <= n {
      nums[j] += n
    } else {
      r = append(r, j + 1)
    }
  }
  return r
}
class Solution {
  function findDuplicates($nums) {
    $r = [];
    $n = count($nums);
    foreach ($nums as $i => $v) {
      $j = ($v - 1) % $n;
      if ($nums[$j] <= $n) $nums[$j] += $n;
      else $r []= $v;
    }
    return $r;
  }
}

哈希集合

var findDuplicates = function(nums) {
  r = [], n = nums.length, s = new Set() // 哈希集合
  for (let i = 0; i < n; i++) {
    if (s.has(nums[i])) r.push(nums[i])
    else s.add(nums[i])
  }
  return r
};
class Solution {
  public List<Integer> findDuplicates(int[] nums) {
    List<Integer> r = new ArrayList<Integer>();
    int n = nums.length;
    HashSet<Integer> s = new HashSet<Integer>();
    for (int i = 0; i < n; i++) {
      if (s.contains(nums[i])) r.add(nums[i]);
      else s.add(nums[i]);
    }
    return r;
  }
}
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        r, s = [], set()
        for num in nums:
          if num in s: r.append(num)
          else: s.add(num)
        return r

哈希映射

function findDuplicates(nums: number[]): number[] {
  const n = nums.length, r = [], h = new Uint32Array(n + 1) // 哈希映射,用 Array / Object.create(null) / Map / WeakMap 亦可
  for (let i = 0; i < n; i++) {
    if (h[nums[i]] === 1) r.push(nums[i])
    else h[nums[i]] = 1
  }
  return r
};
class Solution {
  public List<Integer> findDuplicates(int[] nums) {
    List<Integer> r = new ArrayList<Integer>();
    int n = nums.length;
    HashMap<Integer, Boolean> h = new HashMap<Integer, Boolean>();
    for (int i = 0; i < n; i++) {
      if (h.get(nums[i]) != null) r.add(nums[i]);
      else h.put(nums[i], true);
    }
    return r;
  }
}
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        r, s = [], {}
        for num in nums:
          if num in s: r.append(num)
          else: s[num] = 1
        return r

排序

var findDuplicates = function(nums) {
  nums.sort((a, b) => a - b)
  const r = [], n = nums.length
  for (let i = 1; i < n; i++) {
    if (nums[i] === nums[i - 1]) r.push(nums[i])
  }
  return r
};
func findDuplicates(nums []int) []int {
  sort.Ints(nums)
  r, n := []int{}, len(nums)
  for i := 1; i < n; i++ {
    if nums[i] == nums[i - 1] {
      r = append(r, nums[i])
    }
  }
  return r
}
class Solution {
  function findDuplicates($nums) {
    usort($nums, function($a, $b) {
      return $a - $b;
    });
    $r = [];
    $n = count($nums);
    for ($i = 1; $i < $n; $i++) {
      if ($nums[$i] === $nums[$i - 1]) {
        $r []= $nums[$i];
      }
    }
    return $r;
  }
}

暴力
var findDuplicates = function(nums) {
  const n = nums.length, r = []
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[i] === nums[j]) {
        r.push(nums[i])
      }
    }
  }
  return r
};
正则 · 超时

var findDuplicates = function(nums) {
  return nums.join().match(/\b(\d+)\b(?=.*?\b\1\b)/g) || [];
};
class Solution {
  function findDuplicates($nums) {
    return preg_match_all('/\b(\d+)\b(?=.*?\b\1\b)/', join(' ', $nums), $matches) ? $matches : [];
  }
}
class Solution:
  def findDuplicates(self, nums: List[int]) -> List[int]:
      return re.compile(r'\b(\d+)\b(?=.*?\b\1\b)').findall(','.join(map (str, nums)))

代码
二分查找(对数运算 + 前缀和),滑动窗口:求解《713. 乘积小于 K 的子数组》
根据对数运算性质将相乘转为求和问题,用前缀和优化。二分查找,滑动窗口,求解《713. 乘积小于 K 的子数组》
代码
双指针合并有序数组:求解《88. 合并两个有序数组》和《面试题 10.01. 合并排序的数组》
双指针合并有序数组(合并数组),注意数组越界不同语言的处理方式。求解《88. 合并两个有序数组》和《面试题 10.01. 合并排序的数组》
代码
二维数组自定义函数排序 + 栈:按二维数组自定义函数升序排序,使用栈合并区间,求解《56. 合并区间》和《剑指 Offer II 074. 合并区间》
按二维数组自定义函数升序排序,使用栈合并区间,求解《56. 合并区间》和《剑指 Offer II 074. 合并区间》