class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
}
};
3289. 数字小镇中的捣蛋鬼
数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。
为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。
返回一个长度为 2 的数组，包含这两个数字（顺序任意）。
示例 1：
输入： nums = [0,1,1,0]
输出： [0,1]
解释：
数字 0 和 1 分别在数组中出现了两次。
示例 2：
输入： nums = [0,3,2,1,3,2]
输出： [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。
示例 3：
输入： nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出： [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。
提示：
2 <= n <= 100nums.length == n + 20 <= nums[i] < nnums 中 恰好 包含两个重复的元素。相似题目
原站题解
golang 解法, 执行用时: 5 ms, 内存消耗: 2.6 MB, 提交时间: 2024-09-18 10:05:47
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
xorAll := n ^ (n + 1) // n 和 n+1 多异或了
for i, x := range nums {
xorAll ^= i ^ x
}
shift := bits.TrailingZeros(uint(xorAll))
ans := make([]int, 2)
for i, x := range nums {
if i < n {
ans[i>>shift&1] ^= i
}
ans[x>>shift&1] ^= x
}
return ans
}
// 数学方法
func getSneakyNumbers2(nums []int) []int {
n := len(nums) - 2
a := -n * (n - 1) / 2
b := -n * (n - 1) * (n*2 - 1) / 6
for _, x := range nums {
a += x
b += x * x
}
x := int((float64(a) - math.Sqrt(float64(b*2-a*a))) / 2)
return []int{x, a - x}
}
python3 解法, 执行用时: 41 ms, 内存消耗: 16.5 MB, 提交时间: 2024-09-18 10:05:08
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
xor_all = n ^ (n + 1) # n 和 n+1 多异或了
for i, x in enumerate(nums):
xor_all ^= i ^ x
shift = xor_all.bit_length() - 1
ans = [0, 0]
for i, x in enumerate(nums):
if i < n:
ans[i >> shift & 1] ^= i
ans[x >> shift & 1] ^= x
return ans
# 数学方法
def getSneakyNumbers2(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
a = -n * (n - 1) // 2
b = -n * (n - 1) * (n * 2 - 1) // 6
for x in nums:
a += x
b += x * x
x = int((a - sqrt(b * 2 - a * a)) / 2)
return [x, a - x]