存在重复元素217-力扣（数组+【快排qsort | 哈希uthash】+c | 集合set + py）

古城微笑少年丶 2023-01-17 08:27 110阅读 0赞

题目描述  
给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false  
示例 1:

输入: \[1,2,3,1\]  
输出: true  
示例 2:

输入: \[1,2,3,4\]  
输出: false  
示例 3:

输入: \[1,1,1,3,3,4,3,2,4,2\]  
输出: true

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/contains-duplicate  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
分析：这道题目最容易想到的三种方法如下：

1.暴力求解:双层循环，遍历比较即可。时间复杂度 O ( n 2 ) O(n^2) O(n2)  
2.快排+比较相邻元素：使用快排将数组排序，然后遍历一遍数组比较相邻元素是否相同即可，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)  
3.哈希表和集合：直接比较集合长度是否和原数组长度相同即可。如果采用哈希，依次将数组元素加入哈希表，判重就可以了。时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)。

最初我有第二种和第三种思路，打算用c写，所以就采用了第二种方法，后面发现c有自己优化后的快排方法，并且是优化后的快排，这里记录了[c自己的快排方法][c].

两份实现的快排代码：  
**第一种：自己实现快排**  
关于快排的实现细节可以参考：  
https://www.runoob.com/w3cnote/quick-sort.html

void quick_sort(int s[], int l, int r)
    { 
        if (l < r)
        { 
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            { 
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;  
                if(i < j) 
                    s[i++] = s[j];
                
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;  
                if(i < j) 
                    s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }
    bool containsDuplicate(int* nums, int numsSize){ 
        quick_sort(nums, 0, numsSize-1);
        for(int i = 0; i < numsSize - 1; i++)
        { 
            if(nums[i] == nums[i+1])
            { 
                return true;
            }
        }
        return false;
    }

**利用qsort**

int cmp(const void* a, const void* b)
    { 
    	return *(int *)a - *(int *)b;
    }
    bool containsDuplicate(int* nums, int numsSize){ 
        qsort(nums, numsSize, sizeof(int), cmp);
        for(int i = 0; i < numsSize - 1; i++)
        { 
            if(nums[i] == nums[i+1])
            { 
                return true;
            }
        }
        return false;
    }

第三种思路利用hash，这种思路也是比较容易想到的，但是用c解答有点复杂，我最先用的python中的set，代码如下：

class Solution:
        def containsDuplicate(self, nums: List[int]) -> bool:
            a = set(nums)
            if(len(a) == len(nums)):
                return False
            else:
                return True

后面看了官方的解释，发现可以利用uthash这个开源库，关于这个开源库更多的内容，我也简单总结了一下，请看[uthash][]  
具体实现代码：

struct hashTable { 
        int key;
        UT_hash_handle hh;
    };
    
    bool containsDuplicate(int* nums, int numsSize) { 
        struct hashTable* set = NULL;
        for (int i = 0; i < numsSize; i++) { 
            struct hashTable* tmp;
            HASH_FIND_INT(set, nums + i, tmp);
            if (tmp == NULL) { 
                tmp = malloc(sizeof(struct hashTable));
                tmp->key = nums[i];
                HASH_ADD_INT(set, key, tmp);
            } else { 
                return true;
            }
        }
        return false;
    }

本地测试源码：  
注意，需要引入uthash.h头文件查看https://blog.csdn.net/qq\_38048756/article/details/116235690

#include<stdio.h>
    #include<stdbool.h>
    #include <stdlib.h>
    #include "uthash.h"
    
    struct hashTable { 
        int key;
        UT_hash_handle hh;
    };
    
    bool containsDuplicate(int* nums, int numsSize) { 
        struct hashTable* set = NULL;
        for (int i = 0; i < numsSize; i++) { 
            struct hashTable* tmp;
            HASH_FIND_INT(set, nums + i, tmp);
            if (tmp == NULL) { 
                tmp = malloc(sizeof(struct hashTable));
                tmp->key = nums[i];
                HASH_ADD_INT(set, key, tmp);
            } else { 
                return true;
            }
        }
        return false;
    }
    
    int main()
    { 
    
         int a[10] = { 1, 1110, 2454, 10, -2, 5, 7, 11, 1021, -230};
         bool b = containsDuplicate(a, 10);
         printf("%d", b);
    }

[c]: https://blog.csdn.net/qq_38048756/article/details/116229017
[uthash]: https://blog.csdn.net/qq_38048756/article/details/116235690