文章目錄

• 題目描述
• 思路 & 代碼

題目描述

• 比 leetcode 136要難點
• 注意：空間復雜度要求O(1)，否則用哈希表直接秒殺啦。
• 昨天的筆試，還有刷的面經(jīng)都有這道題。。。今天趕緊補補
  

思路 & 代碼

• 相對于 leetcode 136，這邊多了個分組的考點，相當于分成兩個 leetcode 136
• 如何分組？用整組異或結果，找到第一個 1 位作為location（也就是兩個答案的第一個不同位）
• 以這個location作為標準，把數(shù)組分成兩個子數(shù)組（此位為1的數(shù)，此為為0的數(shù)）
• 可證：兩個子數(shù)組，一定都滿足“數(shù)組中有一個數(shù)出現(xiàn)了一次，其他數(shù)都出現(xiàn)了兩次”
• 證明：首先location本就是把兩答案區(qū)分開的，那么如何證明子數(shù)組中的其他數(shù)都是成對的呢？這個簡單，就是因為原數(shù)組本就是成對的，用location作為標準，也是把元素成對區(qū)分到子數(shù)組中。

class Solution {public int[] singleNumbers(int[] nums) {// 1. 取異或值int XOR = 0;for(int i : nums){XOR ^= i;}// 2. 找到第一個為 1 的位int location = 1;while((XOR & location) == 0){location <<= 1;}// 3. 在兩個子數(shù)組中找到兩個答案int ans1 = 0;int ans2 = 0;for(int i : nums){if((i & location) != 0){ans1 ^= i;}else{ans2 ^= i;}}return new int[]{ans1, ans2};} }

• 無注釋版

class Solution {public int[] singleNumbers(int[] nums) {int xor = 0;for(int temp : nums) {xor ^= temp;}int firstOne = 1;while((xor & firstOne) == 0) {firstOne <<= 1;}int ans1 = 0, ans2 = 0;for(int temp : nums) {if((temp & firstOne) == 0) {ans1 ^= temp;}else {ans2 ^= temp;}}return new int[]{ans1, ans2};} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 56 . 数组中数字出现的次数（Java、位运算）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。