Single Number III (M)
題目
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
Example:
Input: [1,2,1,3,2,5]
Output: [3,5]
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
題意
給定一個陣列，其中只有兩個數只出現了一次，其他所有數都出現了兩次，要求找出這兩個數，
思路
-
最簡單的做法就是使用Set進行操作，將已出現過的從Set中除去，將未出現過的加入到Set中，最后留下的就是要找的兩個數，
-
與 0136. Single Number 使用的方法相同，用異或找出這兩個數a和b，具體方法如下：
- 對所有數進行異或，得到的結果就是a和b的異或(相同的數異或會抵消得到0)，記為xor，
- 因為a和b是不同的數，所以它們二進制的某一位必定不一樣，從右到左找到xor中第一個1(相當于從右到左找到a和b二進制第一個不同的位)，記為pos，如：3 ^ 5 = 011 ^ 101，pos = 010，
- 將nums中所有的數與pos相與，可以將結果分為兩組，區別在于對應二進制位上的數不同，而a和b一定分屬于這兩個組，
- 接著問題就變成和136一樣的情況，將兩組數分別異或，得到的就是a和b，
代碼實作
Java
Set
class Solution {
public int[] singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
set.remove(num);
} else {
set.add(num);
}
}
int[] ans = new int[set.size()];
int index = 0;
for (int num : set) {
ans[index++] = num;
}
return ans;
}
}
位操作
class Solution {
public int[] singleNumber(int[] nums) {
int[] ans = new int[2];
int xor = 0;
for (int num : nums) {
xor ^= num;
}
int pos = 1;
while ((xor & pos) == 0) {
pos <<= 1;
}
for (int num : nums) {
if ((num & pos) == 0) {
ans[0] ^= num;
} else {
ans[1] ^= num;
}
}
return ans;
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumber = function (nums) {
let xor = 0
for (let num of nums) {
xor ^= num
}
let pos = 1
while (!(pos & xor)) {
pos <<= 1
}
let a = 0
let b = 0
for (let num of nums) {
if (num & pos) {
a ^= num
} else {
b ^= num
}
}
return [a, b]
}
參考
LeetCode 260. Single Number III 題解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14508.html
標籤：其他