LeetCode 137 Single Number II(只出现一次的数字 II)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50688103 翻译给定一个整型数组,除了某个元素外其余的均出现了三次。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50688103

翻译

给定一个整型数组,除了某个元素外其余的均出现了三次。找出这个元素。

备注:
你的算法应该是线性时间复杂度。你可以不用额外的空间来实现它吗?

原文

Given an array of integers, every element appears three times except for one. Find that single one.

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

分析

这道题我并没有按照题目线性时间和不使用额外存储的要求来完成,确实很难的一道题……

我也就这水平了,下面的解决方案没有使用额外存储时间不过时间已经超了。

class Solution {
public:

int singleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size() - 1; ++i) {
        if ((nums[i] != nums[i - 1]) && (nums[i] != nums[i + 1]))
            return nums[i];
    }               
    if (nums[0] != nums[1]) return nums[0];
    else if (nums[nums.size() - 1] != nums[nums.size() - 2])
        return nums[nums.size() - 1];
}
};

与之相关的还有两道题,大家可以看看:
LeetCode 136 Single Number(只出现一次的数字)

LeetCode 260 Single Number III(只出现一次的数字 III)(*)

目录
相关文章
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
43 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
|
存储 前端开发 算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
136 0
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
138 0
|
算法 PHP
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
132 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
94 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
95 0
LeetCode 313. Super Ugly Number