劍指 Offer 56 - II. 數組中數字出現的次數 II

2020-08-28 每日精選算法題

題目難度: 中等

原題連結[1]

今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了

題目描述

在一個數組 nums 中除一個數字只出現一次之外，其他數字都出現了三次。請找出那個只出現一次的數字。

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

題目樣例

示例

  • 輸入：nums = [3,4,3,3]
  • 輸出：4
  • 輸入：nums = [9,1,7,9,7,9,7]
  • 輸出：1

題目思考

  1. 還能使用昨天的異或思路嗎?
  2. 可以單獨統計每一位嗎?

解決方案

思路

  • 分析題目, 其他數字都出現了三次, 這時候如果還用異或的話, 這些出現 3 次的數字並不能異或為 0, 而是異或成各自自身, 最終異或的結果相當於每個不同的數都異或了一次, 沒有任何意義
  • 換個角度分析, 如果我們單獨統計每個數字二進位每一位上為 1 的次數並累加, 那麼對於出現 3 次的數而言, 它們的這一位為 1 的次數之和一定是 3 的倍數
  • 很顯然, 加上了單獨出現 1 次的數之後, 這一位上的次數除以 3 的餘數要麼是 0 (代表這個數字這一位是 0), 要麼是 1(代表這個數字這一位是 1), 利用這一點, 我們就能計算出這個數字每一位上到底是 0 還是 1
  • 看到這裡, 結合昨天的劍指 Offer 56 - I. 數組中數字出現的次數 - leetcode 劍指 offer 系列, 相信聰明的大家都能發現一些規律, 我在這裡也總結一下: 其他數字出現偶數次, 某個數字出現奇數次: 全部數字異或其他數字出現偶數次, 某兩個數字各出現奇數次: 異或後根據異或結果的某個 1 分兩類其他數字出現奇數次, 某個數字出現 1 次: 按照二進位每一位統計次數, 然後對這個奇數次取模
  • 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

複雜度

  • 時間複雜度 O(N): 遍歷一遍數組, 然後對於每個數要統計其每一位的次數, 這部分操作是O(32) == O(1), 所以總體複雜度仍為 O(N)
  • 空間複雜度 O(1): 只使用了幾個變量

代碼

class Solution:    def singleNumber(self, nums: List[int]) -> int:        res = 0        for i in range(32):             假設i==1, 對應的mask就是0b000...00010 (共32位, 高位全為0)            mask = 1 << i            cnt = 0            for x in nums:                if x & mask:                     如果次數為1, 則說明出現一次的數字在這一位上為1, 將最終結果或上當前mask即可                res |= mask                 res += mask        return res

參考資料

[1]

原題連結: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

相關焦點

  • 劍指 Offer 56 - I. 數組中數字出現的次數 - leetcode 劍指offer
    就能看到劍指 offer 系列當前連載的所有文章了題目描述一個整型數組 nums 裡除兩個數字之外，其他數字都出現了兩次, 只有一個數字出現一次如何解決?解決方案思路分析題目, 相信大家都能想到計數字典的方案, 就是記錄每個數字的次數, 然後找次數為
  • 劍指 Offer 53 - I. 在排序數組中查找數字 I
    題目難度: 簡單原題連結[1]今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述統計一個數字在排序數組中出現的次數。
  • 劍指 Offer 53 - II. 0～n-1中缺失的數字 - leetcode 劍指offer
    ~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述一個長度為 n-1 的遞增排序數組中的所有數字都是唯一的，並且每個數字都在範圍 0 ～ n-1 之內。在範圍 0 ～ n-1 內的 n 個數字中有且只有一個數字不在該數組中，請找出這個數字。
  • 劍指 Offer 51. 數組中的逆序對 - leetcode 劍指offer系列
    題目難度: 困難原題連結今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。
  • 劍指 Offer 57 - II. 和為s的連續正數序列 - leetcode 劍指offer
    [1]今天繼續更新劍指 就能看到劍指 offer 系列當前連載的所有文章了題目描述輸入一個正整數 target ，輸出所有和為 target序列內的數字由小到大排列，不同序列按照首個數字從小到大排列。;      for r in range(2, target // 2 + 2):             加入當前終點到窗口和中&
  • 劍指 Offer 57. 和為s的兩個數字 - leetcode 劍指offer系列
    , 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指offer 系列當前連載的所有文章了題目描述輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是 s。如果有多對數字的和等於 s，則輸出任意一對即可。
  • 劍指 Offer 66. 構建乘積數組 - leetcode
    [1]今天繼續更新劍指 就能看到劍指 offer 系列當前連載的所有文章了題目描述給定一個數組 A[0,1,…,n-1]，請構建一個數組B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。
  • 劍指Offer 62.圓圈中最後剩下的數字-leetcode
    [1]今天繼續更新劍指 就能看到劍指 offer 系列當前連載的所有文章了題目描述0,1,,n-1 這 n 個數字排成一個圓圈，從數字解決方案思路一個比較容易想到的思路是暴力法, 即使用數組模擬整個過程: 記錄當前起點,
  • 劍指 Offer 58 - II. 左旋轉字符串 - leetcode 劍指offer系列
    [1]今天繼續更新劍指offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部
  • 劍指 Offer 59 - II. 隊列的最大值 - leetcode 劍指offer系列
    [1]今天繼續更新劍指offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 就能看到劍指 offer 系列當前連載的所有文章了題目描述請定義一個隊列並實現函數 max_value 得到隊列裡的最大值
  • 劍指 Offer 61. 撲克牌中的順子-leetcode
    [1]今天繼續更新劍指offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述從撲克牌中隨機抽 5 張牌，判斷是不是一個順子，即這
  • 劍指 Offer 49. 醜數 - leetcode 劍指offer系列
    題目難度: 中等原題連結[1]今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述我們把只包含質因子 2、3 和 5 的數稱作醜數（Ugly Number）。
  • 劍指 Offer 68 - II. 二叉樹的最近公共祖先
    [1]今天繼續更新劍指 就能看到劍指 offer 系列當前連載的所有文章了本篇是劍指 offerp、q 為不同節點且均存在於給定的二叉樹中。二叉搜索樹的最近公共祖先 - leetcode 劍指 offer 系列, 這裡的樹不再是二叉搜索樹, 也就意味著不能根據節點值來判斷應該往那邊遍歷, 只能老老實實逐個節點遍歷了首先嘗試遞歸的做法, 如果我們能得出左右子樹各自的 p/q 節點存在的情況, 再結合當前節點, 就能得出當前節點以及其所有子節點中是否包含 p 和 q那麼在
  • 調整數組順序使奇數位於偶數前面(劍指 Offer 題解,面試)
    調整數組順序使奇數位於偶數前面題目描述需要保證奇數和奇數，偶數和偶數之間的相對位置不變，這和書本不太一樣。解題思路方法一：創建一個新數組，時間複雜度 O(N)，空間複雜度 O(N)。package 劍指offer.調整數組順序使奇數位於偶數前面_21;/*作者 :XiangLin文件 :OrderArray.javaIDE :IntelliJ IDEA*/
  • 劍指 Offer 63. 股票的最大利潤-leetcode
    [1]今天繼續更新劍指offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了這道題是經典的股票問題, 以它為基礎可以延伸很多擴展問題, 我之前也寫過整個股票系列, 一共 6 道題目, 大家感興趣的話在公眾號裡回復
  • MATLAB中找出數組中出現次數最多的數
    對於一個數組，我們有的時候需要找到其中出現次數最多的數，用於後續的算法步驟。對於一下數組，我們很容易看出來，出現次數最多的元素是7。a = [1 2 2 2 2 2 3 3 3 4 5 6 7 8 8 4 5 6 8 9 9 0 7 6 5 7 7 7 7 7 7 7]如果要用MATLAB求出這個數組中的最大元素，我們就要用histc這個函數。第一步，我們先找到數組中的最大值，並寫出數組中可能存在的整數的集合，對於數組A來說，就是1到9。
  • 劍指 Offer 50. 第一個只出現一次的字符 - leetcode 劍指offer
    題目難度: 簡單原題連結[1]今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述在字符串 s 中找出第一個只出現一次的字符。
  • 劍指 Offer 54. 二叉搜索樹的第k大節點 - leetcode 劍指offer
    題目難度: 簡單原題連結[1]今天繼續更新劍指 offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 每日精選算法題, 大家記得關注哦~ 另外在公眾號裡回復 offer 就能看到劍指 offer 系列當前連載的所有文章了題目描述給定一棵二叉搜索樹，請找出其中第 k 大的節點。
  • 劍指 Offer 59 - I. 滑動窗口的最大值 - leetcode 劍指offer系列
    [1]今天繼續更新劍指offer 系列, 老樣子晚上 6 點 45 分準時更新公眾號 就能看到劍指 offer 系列當前連載的所有文章了題目描述給定一個數組 nums 和滑動窗口的大小 k，請找出所有滑動窗口裡的最大值
  • 旋轉數組的最小數字(劍指 Offer 題解Java版)
    旋轉數組的最小數字題目描述題目連結解題思路可以藉助下圖理解過程代碼11. 旋轉數組的最小數字題目描述把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。