个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
27
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现LeetCode(136.单独的数字)由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
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？
Example 1
Input: [2,2,1] Output: 1 。
Example 2
Input: [4,1,2,1,2] Output: 4 。
这道题给了我们一个非空的整数数组，说是除了一个数字之外所有的数字都正好出现了两次，让我们找出这个只出现一次的数字。题目中让我们在线性的时间复杂度内求解，那么一个非常直接的思路就是使用 HashSet，利用其常数级的查找速度。遍历数组中的每个数字，若当前数字已经在 HashSet 中了，则将 HashSet 中的该数字移除，否则就加入 HashSet。这相当于两两抵消了，最终凡事出现两次的数字都被移除了 HashSet，唯一剩下的那个就是单独数字了，参见代码如下:
C++ 解法一:
|
1
2
3
4
5
6
7
8
9
10
11
|
class
Solution {
public
:
int
singleNumber(vector<
int
>& nums) {
unordered_set<
int
> st;
for
(
int
num : nums) {
if
(st.count(num)) st.erase(num);
else
st.insert(num);
}
return
*st.begin();
}
};
|
Java 解法一:
|
1
2
3
4
5
6
7
8
9
|
class Solution {
public int singleNumber(int[] nums) {
Set<
Integer
> st = new HashSet<>();
for (int num : nums) {
if (!st.add(num)) st.remove(num);
}
return st.iterator().next();
}
}
|
题目中让我们不使用额外空间来做，本来是一道非常简单的题，但是由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)，使得不能用排序方法，也不能使用 HashSet 数据结构。那么只能另辟蹊径，需要用位操作 Bit Operation 来解此题，这个解法如果让我想，肯定想不出来，因为谁会想到用逻辑异或来解题呢。逻辑异或的真值表为:
异或运算的真值表如下:
| A | B | ⊕ |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
由于数字在计算机是以二进制存储的，每位上都是0或1，如果我们把两个相同的数字异或，0与0 '异或' 是0，1与1 '异或' 也是0，那么我们会得到0。根据这个特点，我们把数组中所有的数字都 '异或' 起来，则每对相同的数字都会得0，然后最后剩下来的数字就是那个只有1次的数字。这个方法确实很赞，但是感觉一般人不会往 '异或' 上想，绝对是为CS专业的同学设计的好题呀，赞一个~~ 。
C++ 解法二:
|
1
2
3
4
5
6
7
8
|
class
Solution {
public
:
int
singleNumber(vector<
int
>& nums) {
int
res = 0;
for
(auto num : nums) res ^= num;
return
res;
}
};
|
Java 解法二:
|
1
2
3
4
5
6
7
|
class
Solution {
public
int
singleNumber(
int
[] nums) {
int
res =
0
;
for
(
int
num : nums) res ^= num;
return
res;
}
}
|
到此这篇关于C++实现LeetCode(136.单独的数字)的文章就介绍到这了,更多相关C++实现单独的数字内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://www.cnblogs.com/grandyang/p/4130577.html 。
最后此篇关于C++实现LeetCode(136.单独的数字)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(136.单独的数字)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
Java 专家需要您的帮助。 今天我在一次采访中被问到这个问题，但我无法解决。所以我需要一个解决方案来解决这个问题； 反转字符串 Input : Hello, World! Output : oll
目标:单击按钮并将成分作为单独的项目添加到数组中。 当前设置: 这给出:蓝莓芒果柠檬汁 然后我希望能够通过单击按钮将成分作为单独的项目添加到数组中: var allI
如何编写正则表达式来匹配它(参见箭头): "this is a ->'' this is a "test' there is another "test' 第二种情况 /\b'/ Regex Demo
我有一个数组，其中包含有限数量的项目。我想随机删除项目，直到所有项目都被使用过一次。 示例 [1,2,3,4,5] 使用了随机数 5，所以我不想再这样了。使用了随机数 2，所以我不想再这样了。等等..
首先，抱歉，如果这太主观了，我只是不知道还能怎么问/去哪里问。 无论如何，鉴于我最近的所有问题，我准备很快发布一个 Android 应用程序，并且大部分测试都是在我的手机 Droid 上完成的。我真的
这可能不是这个问题的正确位置，如果不合适请随意移动它。我标记为 Delphi/Pascal 因为这是我在 atm 中工作的内容，但这可能适用于我猜的所有编程。 无论如何，我正在做一些代码清理，并考虑将
我像这样分隔了其余 api 的路由。有没有更好的方法来组织路由器？还是我现在的做法没问题？ app.js app.use('/api/auth',auth); 应用程序/ Controller /au
我在 2 个单独的工作表中包含以下数据: 表1: A B C D a ff dd ff ee b 12 10 10 12 表2: A B C
我正在使用 jQuery，并在位于单独 HTML 文件中的表中获取了几行。单击时，每一行都会成功重定向到本地 HTML 文件。 (使用window.location) 我想要实现的目标 我想要完成的是
我有重叠背景图像的问题，当它们重叠时会导致阴影比不重叠时更暗，从而产生不均匀的阴影。 我有一个高度灵活的盒子，带有一些透明的背景图像和阴影以创建漂亮的边框。盒子本质上是 3 个元素。 您可以在此处找到
按照正常的微服务框架，我们希望将每个微服务放入其自己的 git 存储库中，然后为 Service Fabric 项目创建一个存储库。当我们更新其中一个微服务时，Service Fabric 项目将仅重
我想将多个片段嵌入到一个指令中。这是我的设置方式。 Everyone Development (3)
我希望在保留原件的同时将多个文件 gzip 到一个目录中(到多个 .gz 文件中)。 我可以使用这些命令来处理单个文件: find . -type f -name "*cache.html" -exe
有没有办法分别知道每个 Eclipse 插件消耗了多少内存？ 最佳答案 进行堆转储并使用例如分析它Eclipse Memory Analyser . 如需更多信息，请参阅 Analyzing Equi
我们使用cusrom插件并以这种方式定义脚本(这是一个近似的伪代码): //It is common part for every script (1) environments { "env1"
我在控制台应用程序中托管了一个集线器，并有一个 WPF 应用程序连接到它。它工作得很好。然后我将集线器移到一个单独的项目中，并将主机的引用添加到新项目中。现在我收到 500 错误，没有其他详细信息。
是否可以在单独的 JAR 文件中为 JavaBean 构建类？具体来说，JavaBean 在一个 JAR 文件中具有 Bean 和 BeanInfo 类，而自定义属性编辑器类位于另一个 JAR 文件中
好的，所以我有一个 MAF 应用程序，它在单独的应用程序域中加载每个插件。这非常适合我的需要，因为它允许我在运行时动态卸载和重新加载我的插件。 问题是，我需要能够在子应用域中处理未处理的异常，捕获它，
在参加在线数据库类(class)(针对初学者)时，我注意到一个问题，我必须查找涉及...至少两个不同值的查询...例如， ELMASRI 书中的 COMPANY 数据库指出:查找至少从事两个不同项目的
(首先:我已经尝试了涉及边距、边框等的所有选项。) Link to problematic page. Link to similarly constructed, non-problematic p
我是一名优秀的程序员,十分优秀！