C++实现LeetCode(137.单独的数字之二)

2024-02-27 09:20:45

[LeetCode] 137. Single Number II 单独的数字之二

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

这道题是之前那道 Single Number 的延伸，那道题的解法就比较独特，是利用计算机按位储存数字的特性来做的，这道题就是除了一个单独的数字之外，数组中其他的数字都出现了三次，还是要利用位操作 Bit Manipulation 来解。可以建立一个 32 位的数字，来统计每一位上1出现的个数，如果某一位上为1的话，那么如果该整数出现了三次，对3取余为0，这样把每个数的对应位都加起来对3取余，最终剩下来的那个数就是单独的数字。代码如下：

解法一：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j) {
                sum += (nums[j] >> i) & 1;
            }
            res |= (sum % 3) << i;
        }
        return res;
    }
};

还有一种解法，思路很相似，用3个整数来表示 INT 的各位的出现次数情况，one 表示出现了1次，two 表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。

ones 代表第 ith 位只出现一次的掩码变量
twos 代表第 ith 位只出现两次次的掩码变量
threes 代表第 ith 位只出现三次的掩码变量

假设现在有一个数字1，更新 one 的方法就是 ‘亦或' 这个1，则 one 就变成了1，而 two 的更新方法是用上一个状态下的 one 去 ‘与' 上数字1，然后 ‘或' 上这个结果，这样假如之前 one 是1，那么此时 two 也会变成1，这 make sense，因为说明是当前位遇到两个1了；反之如果之前 one 是0，那么现在 two 也就是0。注意更新的顺序是先更新 two，再更新 one，不理解的话只要带个只有一个数字1的输入数组看一下就不难理解了。然后更新 three，如果此时 one 和 two 都是1了，由于先更新的 two，再更新的 one，two 为1，说明此时至少有两个数字1了，而此时 one 为1，说明了此时已经有了三个数字1，这块要仔细想清楚，因为 one 是要 ‘亦或' 一个1的，值能为1，说明之前 one 为0，实际情况是，当第二个1来的时候，two 先更新为1，此时 one 再更新为0，下面 three 就是0了，那么 ‘与' 上t hree 的相反数1不会改变 one 和 two 的值；那么当第三个1来的时候，two 还是1，此时 one 就更新为1了，那么 three 就更新为1了，此时就要清空 one 和 two 了，让它们 ‘与' 上 three 的相反数0即可，最终结果将会保存在 one 中，参见代码如下：

解法二：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= one & nums[i];
            one ^= nums[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

下面这种解法思路也十分巧妙，根据上面解法的思路，我们把数组中数字的每一位累加起来对3取余，剩下的结果就是那个单独数组该位上的数字，由于累加的过程都要对3取余，那么每一位上累加的过程就是 0->1->2->0，换成二进制的表示为 00->01->10->00，可以写出对应关系：

00 (+) 1 = 01

01 (+) 1 = 10

10 (+) 1 = 00 ( mod 3)

用 ab 来表示开始的状态，对于加1操作后，得到的新状态的 ab 的算法如下：

b = b xor r & ~a;

a = a xor r & ~b;

这里的 ab 就是上面的三种状态 00，01，10 的十位和各位，刚开始的时候，a和b都是0，当此时遇到数字1的时候，b更新为1，a更新为0，就是 01 的状态；再次遇到1的时候，b更新为0，a更新为1，就是 10 的状态；再次遇到1的时候，b更新为0，a更新为0，就是 00 的状态，相当于重置了；最后的结果保存在b中，明白了上面的分析过程，就能写出代码如下；

解法三：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); ++i) {
            b = (b ^ nums[i]) & ~a;
            a = (a ^ nums[i]) & ~b;
        }
        return b;
    }
};

到此这篇关于C++实现LeetCode(137.单独的数字之二)的文章就介绍到这了,更多相关C++实现单独的数字之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(79.词语搜索)

[LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th
C++实现LeetCode(73.矩阵赋零)

[LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably
C++实现LeetCode(80.有序数组中去除重复项之二)

[LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus
C++实现LeetCode(75.颜色排序)

[LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2
C++实现LeetCode(74.搜索一个二维矩阵)

[LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great
C++实现LeetCode(85.最大矩形)

[LeetCode] 85. Maximal Rectangle 最大矩形 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Example: Input: [ ["1","0","1","0","0"], ["1
C++实现LeetCode(82.移除有序链表中的重复项之二)

[LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp
C++实现LeetCode(81.在旋转有序数组中搜索之二)

[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.
C++实现LeetCode(76.最小窗口子串)

[LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA
C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you
C++实现LeetCode(136.单独的数字)

[LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
SQL实现LeetCode(180.连续的数字)

[LeetCode] 180.Consecutive Numbers 连续的数字 Write a SQL query to find all numbers that appear at least three times consecutively. +----+-----+ | Id | Num | +----+-----+ | 1 | 1 | | 2 | 1 | | 3 | 1 | | 4 | 2 | | 5 | 1 | | 6 | 2 | | 7 |
C++实现LeetCode(52.N皇后问题之二)

[LeetCode] 52. N-Queens II N皇后问题之二 The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. Example: Inpu
C++实现LeetCode(107.二叉树层序遍历之二)

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3
C++实现LeetCode(108.将有序数组转为二叉搜索树)

[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
C++实现LeetCode(119.杨辉三角之二)

[LeetCode] 119. Pascal's Triangle II 杨辉三角之二 Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0. In Pascal's triangle, each number is the sum of the two numbers directly
C++实现LeetCode(167.两数之和之二 - 输入数组有序)

[LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t
C++实现LeetCode(113.二叉树路径之和之二)

[LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7
C++实现LeetCode(63.不同的路径之二)

[LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二

相关推荐

随机推荐