Single Number and Single Number II

[1] Given an array of integers, every element appears twice except for one. Find that single one.

[2] Given an array of integers, every element appears three times except for one. Find that single one. (better solution is needed)

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

题目中文意思就是说给定一个整数数组,数组中所有元素都出现了两次,只有一个元素只出现了一次,找出这个只出现了一次的元素。

用异或来解决这类问题会非常简单。

代码:

int SingleNumber(int arr[] , int length)
{
    int i , xor;
    for(xor = 0 , i = 0 ; i < length ; ++i)
        xor = xor ^ arr[i];

    return xor;
}

完整代码:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int SingleNumber(int arr[] , int length)
 5 {
 6     int i , xor;
 7     for(xor = 0 , i = 0 ; i < length ; ++i)
 8         xor = xor ^ arr[i];
 9 
10     return xor;
11 }
12 
13 int main()
14 {
15     int arr[] = {2 , 1 , 2 , 1 , 3 , 4 , 3};
16     int length = sizeof(arr)/ sizeof(int);
17 
18     cout<<SingleNumber(arr , length)<<endl;
19 
20     return 0;
21    
22 
23 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 368. Largest Divisible Subset分析代码

这里需要发现一个规律,就是如果result中已经有【1,2】,那么对于要新加进来的数,只要它能整除掉result中最大的数就可以,因为如果先把result按大小...

10710
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

31230
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

232100
来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

22760
来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

26660
来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

11920
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

12030
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

44300
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

276100
来自专栏大史住在大前端

野生前端的数据结构基础练习(6)——集合

3.为Set类增加一个higher(element)方法,该方法返回比传入元素大的元素中最小的一个,并写一段代码来测试该功能。

11730

扫码关注云+社区

领取腾讯云代金券