leetcode系列136-只出现一次的数字

106 阅读 0 评论 70 点赞

我是靠谱客的博主落寞美女，这篇文章主要介绍leetcode系列136-只出现一次的数字，现在分享给大家，希望可以做个参考。

【题目概要】

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
136. Single Number
Given a non-empty 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?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

【思路分析】

注意非空数组中只出现一次的数，其余所有的数都出现了两次，相同的数亦或后为0
示例代码中，给出只出现一次的数，其余数出现K次的代码统一算法

【代码示例1】

复制代码

1
2
3
4
5
6
7
8
9
int singleNumber(int* nums, int numsSize){
    int re = 0;
    for(int i=0; i<numsSize; i++)
    {
        re = re ^ nums[i];
    }
    return re;
}

【代码示例2】

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
【说明】其中每个数出现了K次，将每一位相加，并%k，余数就是只出现一次的数，
有一个地方的问题是temp的类型定义为long型，按道理是int就可以的，leetcode一直报范围错误
int findnums(int *nums, int numsSize, int k)
{
    int re = 0;
    for(int intindex=0; intindex<32; intindex++)
    {
        long temp = 0;
        for(int numcount=0; numcount<numsSize; numcount++)
        {
            temp += (nums[numcount] >> intindex)&0x01 ; 
        }
        re += (temp%k) << intindex;
    }
    return re;
}