在牛客網看到的,一位網友統計的各大廠的工作時間,我印象中像華為,拼多多應該是加班時間比較多的。
不過從統計的數據來看,雖然沒有登頂第一,但也算是比較靠前。
--------------下面是今天的演算法題--------------
來看下今天的演算法題,這題是LeetCode的第260題:只出現一次的數位 III。
問題描述
來源:LeetCode第260題
難度:中等
給你一個整數陣列 nums,其中恰好有兩個元素只出現一次,其余所有元素均出現兩次。找出只出現一次的那兩個元素。你可以按 任意順序返回答案。
你必須設計並實作線性時間復雜度的演算法且僅使用常量額外空間來解決此問題。
範例1:
輸入 :nums = [1,2,1,3,2,5]
輸出 :[3,5]
解釋 :[5, 3] 也是有效的答案。
範例2:
輸入 :nums = [-1,0]
輸出 :[-1,0]
2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
除兩個只出現一次的整數外,nums 中的其他數位都出現兩次
問題分析
這題說的是只有兩個數位出現一次,其他數位都出現兩次,我們把所有數位都異或一遍, 這樣 出現兩次的異或結果 都變成了 0 。
假如這兩個只出現一次的數位分別是 a 和 b ,結果就變成了 a^b ,因為 a 和 b 是不同的數位,所以這個結果肯定不為 0 ,也就是說這個結果的二進制中肯定有 1 ,我們可以根據這個 1 可以把 a 和 b 分到兩個不同的陣列中。
然後在使用前面講的 ,可以求出 a 和 b 。
JAVA:
publicint[] singleNumber(int[] nums) {
int xor = 0;// 保存所有元素異或的結果
for (int num : nums) // 全部都異或一遍
xor ^= num;
xor &= -xor;// 保留xor二進制中最右邊的 1
int[] res = {0, 0};
for (int num : nums) {
// 把陣列分為兩組,每組在分別異或。
if ((num & xor) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
C++:
public:
vector<int> singleNumber(vector<int> &nums){
unsignedint xorRes = 0;// 保存所有元素異或的結果
for (auto num: nums) // 全部都異或一遍
xorRes ^= num;
xorRes &= -xorRes;// 保留xor二進制中最右邊的 1
vector<int> res(2);
for (auto num: nums) {
// 把陣列分為兩組,每組在分別異或。
if ((num & xorRes) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
Python:
defsingleNumber(self, nums: List[int]) -> List[int]:
xor = 0# 保存所有元素異或的結果
for num in nums: # 全部都異或一遍
xor ^= num
xor &= -xor # 保留xor二進制中最右邊的 1
ans1, ans2 = 0, 0
for num in nums:
# 把陣列分為兩組,每組在分別異或。
if (num & xor) == 0:
ans1 ^= num
else:
ans2 ^= num
return [ans1, ans2]