Contains Duplicate (存在重复元素) - Hash Table (哈希表)

你的名字 2022-10-11 13:32 141阅读 0赞

# **Contains Duplicate (存在重复元素) - Hash Table (哈希表)** #

[https://leetcode-cn.com/problems/contains-duplicate/][https_leetcode-cn.com_problems_contains-duplicate]

Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct.

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

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

**Example 1:**

Input: nums = [1,2,3,1]
    Output: true

**Example 2:**

Input: nums = [1,2,3,4]
    Output: false

**Example 3:**

Input: nums = [1,1,1,3,3,4,3,2,4,2]
    Output: true

**Constraints:**

*   1 1 1 <= nums.length <=  1 0 5 10^5 105
 *   − 1 0 9 -10^9 −109 <= nums\[i\] <=  1 0 9 10^9 109 (注意包含负数)

distinct [dɪˈstɪŋkt]：adj. 清晰的，清楚的，明白的，明显的，截然不同的，有区别的，不同种类的，确定无疑的，确实的，确切的
    duplicate [ˈdjuːplɪkeɪt , ˈdjuːplɪkət]：v. 复制，复印，复写，(尤指不必要时) 重复，再做一次 adj. 完全一样的，复制的，副本的 n. 完全一样的东西，复制品，副本
    brute force [bruːt fɔːs]：n. 暴力，强力
    Brute Force，BF：暴力算法

### (1) 排序 ###

对数组中的数字依照从小到大排序，数组中的重复元素一定出现在相邻位置中。我们可以遍历已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

时间复杂度： O ( N l o g N ) O(Nlog^N) O(NlogN)，其中 `N` 为数组的长度，需要对数组进行排序。。

### (2) 哈希表 ###

哈希表使用空间来换取时间，将查找时间从  O ( n ) O(n) O(n) 降低为  O ( 1 ) O(1) O(1)。 哈希表支持以近似恒定的时间进行快速查找。一旦出现冲突 (Collision)，查找用时可能会退化到  O ( n ) O(n) O(n)。仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为  O ( 1 ) O(1) O(1)。

创建哈希表，遍历数组。检测哈希表中是否已存在当前字符，若存在，直接返回结果；若不存在，将当前字符加入哈希表，供后续判断使用。

对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

创建 hash table 特别注意 `x` 有可能为负数，可以将所有 `x` 加上一个值变成正数或者取绝对值，然后再计算 hash idx。

时间复杂度：`O(N)`，其中 `N` 是数组中的元素数量。

## 1. solution 1 - 一遍哈希表 ##

哈希表的实现方式：链地址法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    // 49999 - 40009 - 30011 - 23333 - 13331
    #define MAX_HASH_LEN (23333)  
    #define MAX_ARRAY_LEN (100000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    // -2147483648 ~ 2147483647 = [-2^31, 2^31-1]
    
    typedef struct NODE {
    	struct NODE *prev;
    	struct NODE *next;
    	int idx;
    	int num;
    }Node;
    
    Node hash_table[MAX_HASH_LEN];  // init
    
    Node node_pool[MAX_ARRAY_LEN];
    int node_pool_idx = 0;  // init
    
    void init()
    {
    	node_pool_idx = 0;
    
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(hash_table[i]).prev = (hash_table[i]).next = &(hash_table[i]);
    	}
    }
    
    // 带头节点的双向链表 - 插入函数
    void insert_node(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node_src(Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node(Node *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    int hash_code(const int num)
    {
    	// hash_idx >= 0
    	const int hash_idx = (num + MAX_NUM) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    bool containsDuplicate(int* nums, int numsSize) {
    	bool ret = false;
    
    	// init
    	init();
    
    	// search and insert
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num = nums[i];
    		const int hash_idx = hash_code(num);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *ptr_node = head->next;
    
    		int find_flag = 0;
    		while (ptr_node != head)
    		{
    			if (num == ptr_node->num)
    			{
    				find_flag = 1;
    				break;
    			}
    
    			ptr_node = ptr_node->next;
    		}
    
    		if (1 == find_flag)
    		{
    			ret = true;
    			break;
    		}
    		else
    		{
    			Node *node = &(node_pool[node_pool_idx++]);
    			node->idx = i;
    			node->num = num;
    
    			insert_node(head, node);
    		}
    	}
    
    	return ret;
    }

![在这里插入图片描述][20210630234248245.png_pic_center]

## 2. solution 2 - 一遍哈希表 ##

哈希表的实现方式：链地址法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    // 49999 - 40009 - 30011 - 23333 - 13331
    #define MAX_HASH_LEN (23333)  
    #define MAX_ARRAY_LEN (100000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    // -2147483648 ~ 2147483647 = [-2^31, 2^31-1]
    
    typedef struct NODE {
    	struct NODE *prev;
    	struct NODE *next;
    	int idx;
    	int num;
    }Node;
    
    Node hash_table[MAX_HASH_LEN];  // init
    
    Node node_pool[MAX_ARRAY_LEN];
    int node_pool_idx = 0;  // init
    
    void init()
    {
    	node_pool_idx = 0;
    
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(hash_table[i]).prev = (hash_table[i]).next = &(hash_table[i]);
    	}
    }
    
    // 带头节点的双向链表 - 插入函数
    void insert_node(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node_src(Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node(Node *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    int hash_code(int num)
    {
    	const int num_positive = (num >= 0) ? num : -num;
    	// hash_idx >= 0
    	const int hash_idx = (num_positive) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    int hash_code_src(int num)
    {
    	if (num < 0) {
    		num = -num;
    	}
    	// hash_idx >= 0
    	const int hash_idx = (num) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    bool containsDuplicate(int* nums, int numsSize) {
    	bool ret = false;
    
    	// init
    	init();
    
    	// search and insert
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num = nums[i];
    		const int hash_idx = hash_code(num);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *ptr_node = head->next;
    
    		int find_flag = 0;
    		while (ptr_node != head)
    		{
    			if (num == ptr_node->num)
    			{
    				find_flag = 1;
    				break;
    			}
    
    			ptr_node = ptr_node->next;
    		}
    
    		if (1 == find_flag)
    		{
    			ret = true;
    			break;
    		}
    		else
    		{
    			Node *node = &(node_pool[node_pool_idx++]);
    			node->idx = i;
    			node->num = num;
    
    			insert_node(head, node);
    		}
    	}
    
    	return ret;
    }

![在这里插入图片描述][20210630234456403.png_pic_center]

## 3. solution 3 - 两遍哈希表 ##

哈希表的实现方式：链地址法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    // 49999 - 40009 - 30011 - 23333 - 13331
    #define MAX_HASH_LEN (23333)  
    #define MAX_ARRAY_LEN (100000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    // -2147483648 ~ 2147483647 = [-2^31, 2^31-1]
    
    typedef struct NODE {
    	struct NODE *prev;
    	struct NODE *next;
    	int idx;
    	int num;
    }Node;
    
    Node hash_table[MAX_HASH_LEN];  // init
    
    Node node_pool[MAX_ARRAY_LEN];
    int node_pool_idx = 0;  // init
    
    void init()
    {
    	node_pool_idx = 0;
    
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(hash_table[i]).prev = (hash_table[i]).next = &(hash_table[i]);
    	}
    }
    
    // 带头节点的双向链表 - 插入函数
    void insert_node(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node_src(Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node(Node *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    int hash_code(int num)
    {
    	const int num_positive = (num >= 0) ? num : -num;
    	// hash_idx >= 0
    	const int hash_idx = (num_positive) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    int hash_code_src(int num)
    {
    	if (num < 0) {
    		num = -num;
    	}
    	// hash_idx >= 0
    	const int hash_idx = (num) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    bool containsDuplicate(int* nums, int numsSize) {
    	bool ret = false;
    
    	// init
    	init();
    
    	// insert
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num = nums[i];
    		const int hash_idx = hash_code(num);
    		Node *head = &(hash_table[hash_idx]);
    		Node *node = &(node_pool[node_pool_idx++]);
    		node->idx = i;
    		node->num = num;
    
    		insert_node(head, node);
    	}
    
    	// search
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num = nums[i];
    		const int hash_idx = hash_code(num);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *ptr_node = head->next;
    
    		int find_flag = 0;
    		while (ptr_node != head)
    		{
    			if ((num == ptr_node->num) && (i != ptr_node->idx)) {
    				find_flag = 1;
    				break;
    			}
    
    			ptr_node = ptr_node->next;
    		}
    
    		if (1 == find_flag) {
    			ret = true;
    			break;
    		}
    	}
    
    	return ret;
    }

![在这里插入图片描述][20210706233137891.png_pic_center]

## References ##

[https://leetcode-cn.com/problems/contains-duplicate/][https_leetcode-cn.com_problems_contains-duplicate]

[https_leetcode-cn.com_problems_contains-duplicate]: https://leetcode-cn.com/problems/contains-duplicate/
[20210630234248245.png_pic_center]: /images/20221005/a6b0f1967a6f44baa9ca52b2a8410c19.png
[20210630234456403.png_pic_center]: /images/20221005/c2a95514f0664c1db94d05d011d90d8e.png
[20210706233137891.png_pic_center]: /images/20221005/748ce36f87a5445fa4b04710757e4dc8.png