{"id":8846,"date":"2021-11-27T21:11:55","date_gmt":"2021-11-28T05:11:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8846"},"modified":"2021-11-27T21:12:27","modified_gmt":"2021-11-28T05:12:27","slug":"leetcode-137-single-number-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-137-single-number-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 137. Single Number II"},"content":{"rendered":"\n<p>Given an integer array&nbsp;<code>nums<\/code>&nbsp;where&nbsp;every element appears&nbsp;<strong>three times<\/strong>&nbsp;except for one, which appears&nbsp;<strong>exactly once<\/strong>.&nbsp;<em>Find the single element and return it<\/em>.<\/p>\n\n\n\n<p>You must&nbsp;implement a solution with a linear runtime complexity and use&nbsp;only constant&nbsp;extra space.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,2,3,2]\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [0,1,0,1,0,1,99]\n<strong>Output:<\/strong> 99\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4<\/sup><\/code><\/li><li><code>-2<sup>31<\/sup>&nbsp;&lt;= nums[i] &lt;= 2<sup>31<\/sup>&nbsp;- 1<\/code><\/li><li>Each element in&nbsp;<code>nums<\/code>&nbsp;appears exactly&nbsp;<strong>three times<\/strong>&nbsp;except for one element which appears&nbsp;<strong>once<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bit by bit<\/strong><\/h2>\n\n\n\n<p>Since every number appears three times, the i-th bit must be a factor of 3, if not, that bit belongs to the single number.<\/p>\n\n\n\n<p>Time complexity: O(32n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int singleNumber(vector<int>& nums) {\n    int ans = 0;\n    for (int s = 0; s < 32; ++s) {\n      int mask = 1 << s;\n      int sum = 0;\n      for (int x : nums)\n        if (x &#038; mask) ++sum;\n      if (sum % 3) ans |= mask;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-136-single-number\/\" data-type=\"post\" data-id=\"8843\">\u82b1\u82b1\u9171 LeetCode 136. Single Number<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;nums&nbsp;where&nbsp;every element appears&nbsp;three times&nbsp;except for one, which appears&nbsp;exactly once.&nbsp;Find the single element and return it. You must&nbsp;implement a solution with a linear&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[16,187,177],"class_list":["post-8846","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-mask","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8846","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8846"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8846\/revisions"}],"predecessor-version":[{"id":8848,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8846\/revisions\/8848"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8846"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8846"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8846"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}