在数组中查找两个重复数字的算法,无需排序

在数组中查找两个重复数字的算法，可以使用哈希表来实现。以下是一个简单的 Python 代码示例：

def find_duplicates(arr):
    hash_table = {}
    duplicates = []

    for num in arr:
        if num in hash_table:
            duplicates.append(num)
        else:
            hash_table[num] = True

    return duplicates

这个算法的时间复杂度为 O(n)，其中 n 是数组的长度。它遍历数组中的每个元素，并将其添加到哈希表中。如果元素已经存在于哈希表中，则将其添加到重复数字列表中。最后，返回重复数字列表。

这个算法不需要对数组进行排序，因此它比排序算法更快。同时，它也不需要额外的空间，因为它只使用了一个哈希表来存储数组中的元素。

相关·内容

在排序数组中查找数字

在排序数组中查找数字题目1：数字在排序数组中出现的次数统计一个数字在排序数组中出现的次数。例如，输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3出现了4次，因此输出4....思路： 2分查找数组中的第一个k： 1. 如果中间数字大于k，那么k只可能出现在前半段 2. 如果中间数字小于k，那么k只可能出现在后半段 3....一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。在范围0～n-1内的n个数字中有且仅有一个数字不在该数组中，请找出这个数字。...思路：因为数组有序，因此数组中开始的一些数字与它们的下标相同。如果不在数组中的那个数字记为m，那么所有比m小的数字下标都与它们的值相同。由于m不在数组中，m+1的下标正好是m。...如果中间元素的值与下标不相等，并且前面一个元素的下标与值正好相等，则这个下标就是数组中缺失的数字。 3. 如果中间元素的值与下标不相等，并且前面一个元素的下标与值也不相等，怎查找左边。

3.7K2 0

查找数组中重复的数字

题目来源于《剑指Offer》中的面试题3：找出数组中重复的数字。　　// 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。...数组中某些数字是重复的，但不知道有几个数字重复了，　　// 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。...解决方法有多种，包括数组排序，哈希表法，以及作者推荐的重排数组法。...此处介绍自己的一个做法，以空间换时间，通过新建数组来实现快速查找，具体做法是新建长度为length的数组newArray，初始化值为-1；将numbers数组的值依次作为newArray的下标和对应的值为...: (输出) 数组中的一个重复的数字 // 返回值: // true - 输入有效，并且数组中存在重复的数字 // false - 输入无效，或者数组中没有重复的数字

4K6 0

LeetCode89|在排序数组中查找数字I

1，问题简述统计一个数字在排序数组中出现的次数。...= [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制： 0 数组长度...<= 50000 3，题解思路正常的逻辑思路，比对 4，题解程序 public class SearchTest3 { public static void main(String[] args...count++; } } return count; } } 5，题解程序图片版 6，总结这道题之前的用法竟然是使用键值对集合...HashMap来做的，现在看有点大材小用吧，时间复杂度为O(n)，空间复杂度为O(1)就可以了，这或许就是一点个人的思考吧，不同的时间做法就不一样了

1.3K3 0

Leetcode算法【34在排序数组中查找元素】

在之前ARTS打卡中，我每次都把算法、英文文档、技巧都写在一个文章里，这样对我的帮助是挺大的，但是可能给读者来说，一下子有这么多的输入，还是需要长时间的消化。...所以，后续的ARTS打卡，会尝试先将算法以及英文文档拆分开，11月，收获的季节，让我们继续前行，在秋天收获更多，学习更多。小编与你同行！...Algorithm LeetCode算法在排序数组中查找元素的第一个和最后一个位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array...找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。...在找到第一个数字的前提下，我们从数组的尾部往前遍历，遇到第一个目标数字时，就是我们需要的第二个目标数字（因为最左边有一个已经存在了，所以必然存在一个最右边的数字不会产生找不到的情况）。

2.4K2 0

删除排序数组中的重复数字

题意给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。...样例给出数组nums =[5,6,8,9,9,10]，你的函数应该返回长度5，此时nums = [5,6,8,9,10]。...思路用 2 个指针，一个指有效元素的长度，一个从前向后扫，跳过重复的元素，将不重复的元素依次放到数组前方，最后返回有效元素的长度即可。...nums[++size] = nums[i]; } } return size + 1; } } 原题地址 LintCode：删除排序数组中的重复数字

1.3K2 0

删除排序数组中的重复数字Ⅱ

题意根据删除排序数组中的重复数字中的题意，跟进 ”删除重复数字“，如果可以允许出现两次重复将如何处理？...样例给出数组 A = [1,1,2,2,2,3]，你的函数应该返回长度 5，此时 A = [1,1,2,2,3]。...思路这道题跟删除排序数组中的重复数字差不多，无非就是多判断一次，判断是否有两个连续的重复元素即可。...} i = j; } return index; } } 原题地址 LintCode：删除排序数组中的重复数组

1.2K2 0

【剑指Offer】53.1在排序数组中查找数字 I

NowCoder 题目描述统计一个数字在排序数组中出现的次数 Input: nums = 1, 2, 3, 3, 3, 3, 4, 6 K = 3 Output: 4 解题思路 class Solution...star = binarySearch(nums, target), end = binarySearch(nums, target+1); // 考虑target和target+1，将两个起始位置相减

9403 0

数组中重复的数字

题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。...例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。解题思路最简单的就是用一个数组或者哈希表来存储已经遍历过的数字，但是这样需要开辟额外的空间。...如果题目要求不能开辟额外的空间，那我们可以用如下的方法：因为数组中的数字都在0~n-1的范围内，所以，如果数组中没有重复的数，那当数组排序后，数字i将出现在下标为i的位置。...现在我们重排这个数组，从头到尾扫描每个数字，当扫描到下标为i的数字时，首先比较这个数字(记为m)是不是等于i。...如果是，则接着扫描下一个数字；如果不是，则再拿它和m 位置上的数字进行比较，如果它们相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了），返回true；如果它和m位置上的数字不相等，就把第

2.1K3 0

数组中重复的数字

题目描述：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。...因此不能使用排序的方法，也不能使用额外的标记数组。对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。...在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。...以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复： public int duplicate(

2.3K1 0

数组-在排序数组中查找数字

题目统计一个数字在排序数组中出现的次数。...nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制： 0 数组长度...题解分析本题是一个典型的查找问题。...根据题意可以提取两点信息：数组本身是有序的需要输出target出现的次数因此，本题转换成查找边界问题： target第一次出现的位置 target最后一次出现的位置时间复杂度：O(logN) 空间复杂度...if (nums[mid] <= target) { left = mid + 1; // 保证nums[left]最终是target最后一次出现的下一个位置或者数组的尾的下一个位置

9761 0

【剑指offer|5.在排序数组中查找数字I】

0.在排序数组中查找数字I 1.低效率方法© 通过二分查找找到目标值, 局部时间复杂度O(logN); 然后在目标值左右扫描, 直到分别扫描到第一个3和最后一个3, 因为要查找的数字在长度为N的数组中可能出现...© 我们考虑怎样更好地利用二分查找，在前面的算法中，时间主要消耗在一个一个找target，从而找到第一个target和最后一个target上，所以我们能不能用通过某种方式更快地直接找到第一个target...二分查找算法总是先拿数组中间的数和target作比较，如果中间的数字比target大，则target有可能出现在前半段，下一轮我们只用在前半段找就可以了；如果中间的数字比target小，则target有可能出现在后半段...如果中间的数字和target相等那？...我们先判断这个数字是不是第一个target，如果这个数字的前一个数字不等于target, 那么这个数字刚好就是第一个target ；如果这个数字的前一个数字等于target, 那么第一个target一定就在前半段

8694 0

查找算法：在双重排序的数组中进行快速查找

假设A是一个n\*n的二维数组。它的行和列都按照升序排列，给定一个数值x，设计一个有效算法，能快速在数组A中查找x是否存在。...同时考虑一个算法效率的下界，也就是无论任何算法，它的时间复杂度都必须高于某个给定水准。这道题难度不大，看到排序数组时，我们就应该本能的考虑到使用二分查找。...imageMogr2/auto-orient/strip) 最简单的方法是，循环遍历整个二维数组，依次查找给定元素是否与给定元素一样，当然这么做的算法复杂度是O(n^2)，因为没有理由到排序特性，因此效率不高...在第二行中，折半查找到7时，7比6.5大，此时根据行和列都升序排列的条件，我们可以忽略掉7开始的子矩阵，也就是[7,8,11,12,15,16]，由此一下子就排除掉无需考虑的一大堆元素。...在竖直方向上查找时，如果元素值比给定数值小，那么该元素同行内左边元素都可以无需考虑，如果元素比给定值大，那么位于元素下方的元素都可以不用考虑，如果找到一个比给定数值大的最小元素时，如果数组存在给定数值大小相同的元素

1.1K1 0

算法-删除已排序数组中的重复项

，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。...示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。...你不需要考虑数组中超出新长度后面的元素。...，比如说判断一个重复项，则继续增大，直至重复的数组元素这段代码我们可以这样考虑：实际上第一段代码无论是否数组有所重复，都要将数组遍历的下标向前推，所以不妨就将其放在for循环中，因为下标 j 其自增只要不越界...只有不重复，在赋值并自增；可见一点：逻辑化简后，代码段更加精炼，并且更加清晰明了 2.我们对于这种判断是需要设计两个快、慢指针；快指针始终在增加，慢指针满足一定条件才增加；这样一来就起到了删除数组元素

3.5K2 0

数组中的重复数字

"""描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。...例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。...存在不合法的输入的话输出-1数据范围：0\le n \le 10000 \0≤n≤10000进阶：时间复杂度O(n)\O(n) ，空间复杂度O(n)\O(n)示例1输入：[2,3,1,0,2,5,3]复制返回值...：2复制说明：2或3都是对的数据范围：0\le n \le 10000 \0≤n≤10000进阶：时间复杂度O(n)\O(n) ，空间复杂度O(n)\O(n)"""# @param numbers int...整型一维数组# @return int整型#from typing import Listclass Solution: def duplicate(self , numbers: List[int

1.4K1 0

算法-数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数，比如排序数组为{1,2,3,3,3,4,5}，那么数字3出现的次数就是3。...2.除此之外，我们注意到，任务本质上是查找问题，而且是排序好的数组，可以尝试用二分查找算法，这样我们可以找到一个3，然后根据这个3向数组的两端遍历，找到所有的3，但是如果3是n个呢？...3.最后，我们发现在排序数组中，如果我们知道了第一个3和最后一个3出现的位置，那么其实也就知道了个数，那么我们能否在第一次使用二分查找之后，继续使用二分法，找到两端的3？...如果中间数字右侧相邻的数不是3，那么最后一个3一定就在中间： ? 所以，我们可以把找第一个和最后一个分成两个问题来考虑，用两个函数分别返回在数组中的位置，那么他们的差值+1就是个数。...个人感觉，二分查找的关键在于用一种规则，让每次查找之后的范围都可以减半，一次来降低时间复杂度，所以改进的二分查找可以很多问题中灵活使用，除了这个，在旋转数组的最小数字问题中也可以用到，甚至在旋转数组的最小数字中

9005 0

JavaScript算法题：查找数字在数组中的索引

我们必须对数字数组进行升序排序，并找出给定数字在该数组中的位置。算法说明将值（第二个参数）插入到数组（第一个参数）中，并返回其在排序后的数组中的最低索引。返回的值应该是一个数字。...解决方案＃1：`.sort()`，. indexOf`()` PEDAC 理解问题：有两个输入：一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后，再返回它的索引。...示例/测试用例：我们不知道输入的数组是以哪种方式排序的，但是提供的测试用例清楚地表明，输入的数组应该从小到大进行排序。请注意，在最后一个测试用例中存在边界问题，其中输入数组是一个空数组。...我们的目标是将输入的数字在输入数组后中排序后，再返回它的索引。示例/测试用例：我们不知道输入的数组是以哪种方式排序的，但是提供的测试用例清楚地表明，输入的数组应该从小到大进行排序。...这个解决方案需要考虑两个边界情况：如果输入数组为空，则我们需要返回 0，因为 num 将是该数组中的唯一元素，所以它在索引为 0 的位置。

2K2 0

删除排序数组中的重复项删除排序数组中的重复项 II

Remove Duplicates from Sorted Array 题目大意对排好序的list去重，输出去重后长度，并且不能创建新的数组解题思路快慢指针代码官方答案数组完成排序后，我们可以放置两个指针...当我们遇到 nums[j] \neq nums[i]nums[j]≠nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]nums[j]）的值复制到 nums[i + 1]nums...然后递增 ii，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。...Remove Duplicates from Sorted Array（从一个有序的数组中去除重复的数字，返回处理后的数组长度）的基础上，可以使每个数字最多重复一次，也就是说如果某一个数字的个数大于等于...2个，结果中应保留2个该数字。

6.5K2 0

删除排序数组中的重复数字 II

跟进“删除重复数字”：如果可以允许出现两次重复将如何处理？允许出现两次重复的意思就是说两次重复不算重复，和一次重复的略有不同，只需要一个计数器来计算是否有两次重复就可以了。

5172 0

算法养成记：删除排序数组中的重复项

，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。...示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。...你不需要考虑数组中超出新长度后面的元素。说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。...也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。...// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } ? ? ? ?

4172 0

在MATLAB中实现高效的排序与查找算法

在MATLAB中实现高效的排序与查找算法在MATLAB中，排序与查找是常见且重要的算法任务。在处理大量数据时，算法的效率直接影响程序的运行速度和性能。...常见的查找算法有顺序查找、二分查找等。二分查找是一种高效的查找算法，适用于已排序的数组。其基本思想是每次将查找范围缩小一半，直到找到目标元素。...二分查找：时间复杂度为 O(log n)，仅适用于已排序数组。四、实用技巧与优化 4.1 选择合适的排序算法在选择排序算法时，我们需要根据具体的应用场景来决定使用哪种算法。...在MATLAB中，内置的sort函数通常会选择最快的排序算法，因此在实际应用中，除非有特殊的性能需求，否则可以直接使用MATLAB的内置排序功能。...：标准的归并排序需要额外的空间来存储两个子数组。

2791 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

在数组中查找两个重复数字的算法,无需排序

相关·内容

在排序数组中查找数字

查找数组中重复的数字

LeetCode89|在排序数组中查找数字I

Leetcode算法【34在排序数组中查找元素】

删除排序数组中的重复数字

删除排序数组中的重复数字Ⅱ

【剑指Offer】53.1在排序数组中查找数字 I

数组中重复的数字

数组中重复的数字

数组-在排序数组中查找数字

【剑指offer|5.在排序数组中查找数字I】

查找算法：在双重排序的数组中进行快速查找

算法-删除已排序数组中的重复项

数组中的重复数字

算法-数字在排序数组中出现的次数

JavaScript算法题：查找数字在数组中的索引

删除排序数组中的重复项删除排序数组中的重复项 II

删除排序数组中的重复数字 II

算法养成记：删除排序数组中的重复项

在MATLAB中实现高效的排序与查找算法

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐