栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]
示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]
 

限制:

2 <= nums.length <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 

解法:

分组异或。在此之前我做过“一个数组里只有一个数只出现一次,其余出现两次”和“一个数组里只有一个数只出现一次,其余出现三次”。本题可以转换为上面的题。本题有两个数只出现一次,那么我们只需要把这两个数分开异或就好了,那么怎么分开呢?

假设那个只出现一次的两个数为a,b。那么我们对数组的所有元素进行异或,可得到a^b,a^b的结果为a与b二进制中不一样的地方。那么我们可以找到a^b中的一个1,根据这个1的位置,对数组进行分组异或。

class Solution {

public:
    vector singleNumbers(vector& nums) {
        int sum=0;
        for(auto num:nums)
            sum^=num;
        auto getPos=[&](int x)
        {
            for(int i=0;i>=1;
            }
            return 0;
        };
        int pos=getPos(sum);
        int p=0,q=0;
        for(auto num:nums)
        {
            if(num&1< 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/695461.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号