程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Single Number II

leetcode筆記:Single Number II

編輯:C++入門知識

leetcode筆記:Single Number II


一.題目描述

這裡寫圖片描述

二.解題思路

這道題與Single Number(數組中其他數出現兩次,僅有一個出現一次的)有所不同,本題變為序列中有一個數出現一次,其他元素出現了三次,同樣要求時間復雜度為線性,空間復雜度為常數。事實上,該算法仍可以借助位運算來實現。

首先需要確定int類型數據的長度:intWidth = sizeof(int) * 8,可以用intWidth大小的變量來存儲數組中每個元素的各個二進制位上1 出現的次數,最後 在進行 模3 操作,如果為1,那說明這一位是要找元素二進制表示中為 1 的那一位。

一個例子

以下有一組序列,寫出每個數的二進制形式:

13:1 1 0 1
13:1 1 0 1
13:1 1 0 1
8: 1 0 0 0
9: 1 0 0 1
9: 1 0 0 1
9: 1 0 0 1

統計每一位二進制位上 1 出現的次數,由高位到低位依次為:7 3 0 6 ,最後對7 3 0 6 中各元素進行模3(%3),得到:1 0 0 0 ,即為出現一次的數的二進制表示,返回該值即可。實際上對於該命題的擴展,即:若存在一序列,除了一個數只出現一次,其他數均出現k次的情況下,同樣可使用以上方法,對每一位二進制位上 1 出現的次數進行統計,最後進行模k(%k)即得到目標值。

三.示例代碼

// 時間復雜度O(n),空間復雜度O(1)
class Solution 
{
public:
    int findSingleNumber(int A[], int n) 
    {
        const int intWidth = sizeof(int) * 8;
        int bitNum[intWidth] = { 0 };  // initialize
        int res = 0;
        for (int i = 0; i < intWidth; i++){
            for (int j = 0; j < n; j++){
                bitNum[i] += (A[j] >> i) & 1;
            }
            res |= (bitNum[i] % 3) << i;
        }
        return res;
    }
};

四.總結

閱讀了網上其他博文,發現事實上有更為高效的方法,其基本思路是利用三個變量分別保存各個二進制位上 1 出現一次、兩次、三次的分布情況,最後只需返回第一個變量就行了。這種方法我本人並沒有實現,日後再繼續研究。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved