leetcode只出现一次的数字

153 阅读 0 评论 101 点赞

我是靠谱客的博主甜甜萝莉，这篇文章主要介绍leetcode只出现一次的数字，现在分享给大家，希望可以做个参考。

只出现一次的数字

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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

第一种解法：

思考：首先不考虑说明部分，不考虑空间复杂度和时间复杂度，看到题目中有个限制，除了唯一元素外，其他元素都均出现两次，遍历整个数组，把出现两次的元素都标记0，最后再遍历一把数组。如果全部时0，返回0；负责返回唯一一个非0.

缺点：时间复杂度高，并且改变了原数组元素的值，可以考虑把数组复制一下，但是空间复杂度会提升。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int singleNumber(int* nums, int numsSize){
    int a,i,j;

    for(i=0; i<numsSize; i++)
    {
        if(nums[i] == 0)
            continue;
        else
            a = nums[i];
        for(j = i+1; j < numsSize; j++)
        {
            if(a == nums[j])
            {
                nums[i] = 0;
                nums[j] = 0;
                break;
            }
            else
                continue;
        }
    }
    i = 0;
    while(i<numsSize && nums[i] == 0)
        i++;
    return i == numsSize ? nums[numsSize-1] : nums[i];
}

时间复杂度：O(n*n)

空间复杂度：O(1)

第二种解法：最优解且符合题目要求

（看别人题解）：妙妙妙

思考：

复制代码

1
2
3
4
异或三定律：
a^a = 0;
a^0 = a;
a^b^c = a^(b^c);//异或交换律 结合律？

考虑只有一个元素只出现一次，其他均出现2次，把所有元素异或一把，搞定

复制代码

1
2
3
4
5
6
int singleNumber(int* nums, int numsSize){
    int ret = 0;//一定记得初始化为0，不然可能会出现异常
    for(int i = 0; i < numsSize; i++)
        ret ^= nums[i];
    return ret;
}

第三种解法：略微复杂，且空间浪费较多，但是比较通用，不仅针对本题其他元素出现2，出现N次也可满足--leetcode 137. 只出现一次的数字 II

构建一个链表，每一个链表存储元素值及其出现次数，轮询整个数组，把每一值出现的次数存在链表中，最后再轮询链表，找到只出现一次的元素。

复制代码

//这个程序中为了方便，使用链表头尾指针
typedef struct Node{
    int val;
    int count;
    struct Node *next;
}node;
//传进来的tail一定要是**，采用尾插法，需要修改尾指针的值
void insert_node(node* head, node** tail, int data)
{
    node * p = head->next;
    while(p != *tail)
    {
        if(p->val == data)
        {
            p->count++;
            return;
        }
        else
            p = p->next;
    }

node* newnode = (node *)malloc(sizeof(struct Node));
    newnode->val = 0;
    newnode->count = 0;
    newnode->next = NULL;
    (*tail)->val = data;
    (*tail)->count++;
    (*tail)->next = newnode;
    *tail = newnode;
    return;
}
int find(node* head, node *tail)
{
    int ret;
    node *p = head;
    node *q = NULL;
    while(p != tail)
    {
        if(p->count == 1)
            ret = p->val;
        q = p->next;
        free(p);
        p = q;
    }
    free(tail);
    return ret;
}

int singleNumber(int* nums, int numsSize){

node* head = (node *)malloc(sizeof(struct Node));
    head->val = 0;
    head->count = 0;
    node* tail = (node *)malloc(sizeof(struct Node));
    head->next = tail;
    tail->val = 0;
    tail->count = 0;
    tail->next = NULL;
    int i = 0;
    for(;i < numsSize; i++)
        insert_node(head,&tail,nums[i]);
    return find(head,tail);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//这个程序中为了方便，使用链表头尾指针
typedef struct Node{
    int val;
    int count;
    struct Node *next;
}node;
//传进来的tail一定要是**，采用尾插法，需要修改尾指针的值
void insert_node(node* head, node** tail, int data)
{
    node * p = head->next;
    while(p != *tail)
    {
        if(p->val == data)
        {
            p->count++;
            return;
        }
        else
            p = p->next;
    }

    node* newnode = (node *)malloc(sizeof(struct Node));
    newnode->val = 0;
    newnode->count = 0;
    newnode->next = NULL;
    (*tail)->val = data;
    (*tail)->count++;
    (*tail)->next = newnode;
    *tail = newnode;
    return;
}
int find(node* head, node *tail)
{
    int ret;
    node *p = head;
    node *q = NULL;
    while(p != tail)
    {
        if(p->count == 1)
            ret = p->val;
        q = p->next;
        free(p);
        p = q;
    }
    free(tail);
    return ret;
}

int singleNumber(int* nums, int numsSize){

    node* head = (node *)malloc(sizeof(struct Node));
    head->val = 0;
    head->count = 0;
    node* tail = (node *)malloc(sizeof(struct Node));
    head->next = tail;
    tail->val = 0;
    tail->count = 0;
    tail->next = NULL;
    int i = 0;
    for(;i < numsSize; i++)
        insert_node(head,&tail,nums[i]);
    return find(head,tail);

}

137题提交

第四种解法：hashmap--参考多数元素（第三种解法，我自己写的hashmap）

第五种解法：go语言，利用map

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func singleNumber(nums []int) int {
    var numsinfo map[int] int
    numsinfo = make(map[int] int)
    for i :=0 ; i < len(nums); i++ {
        numsinfo[nums[i]]++; 
    }
    for key,value := range numsinfo {
        if value == 1{
            return key;
        }
    }
    return 0;
}

一种幼稚的想法：

复制一个数组出来，然后根据对应输入数组元素的下标++，最后遍历新数组，值为1的下标返回即为只出现一次的元素

问题：输入数组 nums[] = {5}，立马段错误

解决：创建一个int类型范围大小的数组，但是这个不现实，只理论可行。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int singleNumber(int* nums, int numsSize){
    int *a = (int *)malloc(numsSize*sizeof(int));
    for(int i = 0;i < numsSize; i++)
        a[i] = 0;
    for(int i = 0;i < numsSize; i++)
        a[nums[i]]++;
    for(int i = 0; i < numsSize; i++)
        if(a[i] == 1)
        {
            free(a);
            return i;
        }
    free(a);
    return 0;
}