Single Number

简介: Given an 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?   注意:多关键字的multimap不能使用下标操作。

Given an 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?

 

注意:多关键字的multimap不能使用下标操作。

C++代码如下:

#include<iostream>
#include<map>
using namespace std;

class Solution
{
public:
    int singleNumber(int A[],int n)
    {
        multimap<int,int> mp;
        int i;
        for(i=0;i<n;i++)
        {
            mp.insert({A[i],i});
        }
        auto map_it=mp.begin();
        while(map_it!=mp.end())
        {
            auto tmp=map_it;
            tmp++;
            if((tmp)==mp.end())
                return (map_it)->first;
            if(map_it->first!=(tmp)->first)
                break;
            map_it++;
            map_it++;
        }
        return map_it->first;
    }
};

int main()
{
    Solution s;
    int arr[]={2,4,2,4,5};
    cout<<s.singleNumber(arr,5)<<endl;
}

 

第二遍刷:

    int singleNumber(int A[],int n)
    {
        multiset<int> st;
        int i;
        for(i=0;i<n;i++)
            st.insert(A[i]);
        for(i=0;i<n;i++)
            if(st.count(A[i])!=2)
                break;
        return A[i];
    }

 

相关文章
|
5月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
21 0
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
|
算法
LeetCode 260. Single Number III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
73 0
LeetCode 260. Single Number III
|
PHP
Leetcode 之 PHP 解析 (260. Single Number III)
Leetcode 之 PHP 解析 (260. Single Number III)
79 0
Leetcode 之 PHP 解析 (260. Single Number III)
|
机器学习/深度学习
Leetcode-Easy 136. Single Number
Leetcode-Easy 136. Single Number
94 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. 说明: 你的算法应该具有线性时间复杂度。
952 0
LeetCode 260 Single Number III(只出现一次的数字 III)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686236 原文 给定一个数字数组nums,其中有两个元素只出现一次,而其他所有元素均出现两次。
1221 0
|
算法
LeetCode 136 Single Number(只出现一次的数字)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686403 翻译 给定一个整型数组,除了某个元素外其余元素均出现两次。
983 0
|
存储 算法
LeetCode 137 Single Number II(只出现一次的数字 II)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50688103 翻译 给定一个整型数组,除了某个元素外其余的均出现了三次。
1483 0
Single Number and Single Number II
[1] Given an array of integers, every element appears twice except for one. Find that single one.
741 0