Single Number and Single Number II

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

 

[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 }

 

 

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号: 猿人谷
如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】
如果您希望与我交流互动,欢迎关注微信公众号
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。

目录
相关文章
|
6月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
22 0
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
|
算法
LeetCode 260. Single Number III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
75 0
LeetCode 260. Single Number III
|
PHP
Leetcode 之 PHP 解析 (260. Single Number III)
Leetcode 之 PHP 解析 (260. Single Number III)
81 0
Leetcode 之 PHP 解析 (260. Single Number III)
|
机器学习/深度学习
Leetcode-Easy 136. Single Number
Leetcode-Easy 136. Single Number
96 0
Leetcode-Easy 136. Single Number
LeetCode 136:只出现一次的数字 Single Number
题目: 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 Given a non-empty array of integers, every element appears twice except for one. Find that single one. 说明: 你的算法应该具有线性时间复杂度。
954 0