5 种方法交换变量，用绝对值和求模标记，用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法：求解《442. 数组中重复的数据》
2022-05-08 13:16:43
利用 5 种方法交换变量，用绝对值和求模标记，用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法求解《442. 数组中重复的数据》
交换变量的 5 种方法
中间变量法
t = a
a = b
b = t解构赋值法
[a, b] = [b, a]a, b = b, aa, b = b, alist($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)))
