数组中重复的数字

2021-09-23 11:14

阅读:961

标签:异常   amp   solution   code   哈希   利用   数组   rac   round   题目:   在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应第一个重复的数字是2。 来源:数组中重复的数字" href="https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&&tqId=11203&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking" target="_blank">https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&&tqId=11203&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking 思路:   第一种思路:寻找重复的数字最容易想到的就是先排序后查找,因为如果数字出现重复,那么排序后相邻的数字必定相同,但是排序算法的时间复杂度是O(n*logn)。   第二种思路:借助哈希表,遍历数组时,判断哈希表内是否含有该数字,如果没有就加入哈希表,如果有,则找到一个重复的数字,这种方法虽然只需要遍历一次数组,但是需要O(n)的空间复杂度。   第三种思路:充分利用题目所给的信息,如果数组是无重复的,那么扫描到下标 i 时,数组值应该也是 i。 如果有重复数字时,首先比较下标为 i 的数字(x)是否等于 i,如果等于,遍历到下一个数字;如果不等于,则应当拿它与下标为x的数据比较,如果相等,则找到重复的数字,如果不等,则将下标为 i 的数字与下标为x的数字交换,使下标为 i 的数字x放到正确的位置,重复上述过程。  Python解法(思路二): 1 class Solution: 2 def duplicate(self, numbers, duplication): 3 if numbers is None or len(numbers) len(numbers)-1: 7 return False 8 hash_table = [] 9 for i in range(len(numbers)): 10 if numbers[i] not in hash_table: 11 hash_table.append(numbers[i]) 12 else: 13 duplication[0] = numbers[i] 14 return True 15 return False C++解法(思路三): 1 class Solution { 2 public: 3 bool duplicate(int numbers[], int length, int* duplication) { 4 if (numbers == NULL || length length - 1) 8 return false; 9 for (int i = 0; i


评论


亲,登录后才可以留言!