我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題56 - II. 陣列中數字出現的次數 II
題目
在一個陣列 nums 中除一個數字只出現一次之外，其他數字都出現了三次，請找出那個只出現一次的數字，
示例 1：
輸入：nums = [3,4,3,3]
輸出：4
示例 2：
輸入：nums = [9,1,7,9,7,9,7]
輸出：1
限制：
- 1 <= nums.length <= 10000
- 1 <= nums[i] < \(2^{31}\)
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
以下是一般化的思路分析：
考慮把數的出現對應到二進制位的bit上，在bit上的表現為0的忽略，只考慮為1的；
那么對于所有數出現了n次，而只有一個數出現了1次的陣列，統計所有數的bit位情況：
- 某個數出現了n次，那么該數對應bit位為1的統計次數必為n的倍數或者n的倍數+1；
- 某個數只出現了一次，那么該數對應bit位為1的統計次數必為n的倍數+1；
根據以上的條件，只要統計所有bit位為1的出現次數并對n取模，那么余下的bit位組成的數就是只出現一次的數；
思路1-統計bit位為1的次數并對3取模
根據以上的分析，對于本題n取3即可，因為是int型別，故統計bit的陣列長度取32即可；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路2-3進制統計
思路決議：這個思路考慮的是對每一個bit位，統計其出現次數并以3進制記錄，表現是一個有限狀態機；
圖解：
對于one的計算，若新一個值val為0則不影響，若為1時：
- \(two==0\)：
- \(one==0，則one=1\)；
- \(one==1，則one=0\)； - \(two==1\)：
- \(則one=0\);
以上用位運算可以簡化為：
- \(one = one ^ val & ~two\)；
one ^ val 對應當two為0時，此時若val為0則one仍為原值，若val為1，那么若one為1則進位后one將變為0，若one為0，則無進位，one變為1，這個程序等價于one ^ val；
& ~two 對應當two為0時，one的結果取決與前面段，若two為1，那么one只能取0；
對于two的計算，實際上跟one的計算邏輯一樣的，對于計算后的one，為0時，two可取0或1，取決于two ^ val，若one為1，那么two必只能取0；
所以：
- \(two = two ^ val & ~one\);
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月17日 下午2:34:15
* @Description: 面試題56 - II. 陣列中數字出現的次數 II
*
*/
public class LeetCode_Offer_56_2 {
}
class Solution_Offer_56_2 {
/**
* @author: ZhouJie
* @date: 2020年5月17日 下午2:34:51
* @param: @param nums
* @param: @return
* @return: int
* @Description: 1-統計各個 bit位1的出現次數，對要求的次數取模運算；
*
*/
public int singleNumber_1(int[] nums) {
int[] bit = new int[32];
int counts = 3, rst = 0, b = 0;
for (int val : nums) {
for (int i = 0; i < 32; i++) {
b = val >>> i;
// 之后的bit位均為0，則停止統計，無意義
if (b == 0) {
break;
}
// 當前要統計的bit為1才統計
if ((b &= 1) == 1) {
bit[i]++;
}
}
}
for (int i = 0; i < 32; i++) {
// 若對應bit位統計到的1不是counts的倍數，則將其置為1；
if (bit[i] % counts != 0) {
rst |= 1 << i;
}
}
return rst;
}
/**
* @author: ZhouJie
* @date: 2020年5月17日 下午6:00:06
* @param: @param nums
* @param: @return
* @return: int
* @Description: 2-用兩個數的對應bit位的00來統計該bit位上1的出現次數：
* 00代表1出現0次；
* 01代表1出現1次；
* 10代表1出現2次；
* 00代表1出現3次；
*
* 即00代表1出現3n次，對于本題，最后每個bit位的情況只可能為00或者01；
*
*
*/
public int singleNumber_2(int[] nums) {
int one = 0, two = 0;
for (int val : nums) {
one = one ^ val & ~two;
two = two ^ val & ~one;
}
return one;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185740.html
標籤：Java