鱼C论坛

 找回密码
 立即注册
查看: 2410|回复: 3

[技术交流] 136_只出现一次的数字

[复制链接]
发表于 2019-6-15 10:09:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
/*
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
*/
int singleNumber(int* nums, int numsSize){
    
    int ret_val = 0;
    int i = 0;
    
    for(i = 0; i <numsSize;i++)
    {
        ret_val ^= nums[i];
    }
    return ret_val;

}

/*
最近提交结果:
通过
显示详情
执行用时 :12 ms, 在所有C提交中击败了99.46% 的用户
内存消耗 :7.9 MB, 在所有C提交中击败了40.52%的用户


16 / 16 个通过测试用例 状态:通过
执行用时:12 ms
提交时间:0 分钟之前

*/
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-6-15 10:11:08 | 显示全部楼层
利用异或特性~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-6-15 10:56:50 | 显示全部楼层
看不懂你说的异或怎么在你的code里体现,能解释一下吗,我用python写了一个,runtime:60ms

class Solution:
    def singleNumber(self, L):
        head = self.get_head(L)
        tail = self.get_tail(L)
        if head in tail:
            L1 = self.delete(head,tail)
            self.singleNumber(L1)
        else:
            print(head)
        
    def get_head(self,L):
        if len(L) >= 1:
            return L[0]
        else:
            return []

    def get_tail(self,L):
        if len(L) >= 1:
            return L[1:]
        else:
            return []

    def delete(self,X, L):
        if L == []:
            return []
        else:
            if X == self.get_head(L):
                return self.delete(X, self.get_tail(L))
            else:
                return [self.get_head(L)] + self.delete(X, self.get_tail(L))
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-6-15 15:25:57 | 显示全部楼层
本帖最后由 风扫地 于 2019-6-15 17:54 编辑
Seawolf 发表于 2019-6-15 10:56
看不懂你说的异或怎么在你的code里体现,能解释一下吗,我用python写了一个,runtime:60ms


a ^ a = 0;
0 ^ b = b;
a ^ b ^ c = a ^ (b ^ c);
a ^ b ^ c = a ^ c ^ b;

异或操作满足结合律和交换律。
在本题中,出现偶数次的数在异或操作后会变成0,出现奇数次的数会最后剩下来。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 21:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表