【剑指 Offer】03.数组中重复的数字
2024-10-01 12:12:57
题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
Java
import java.util.HashSet;
import java.util.Set;
class Solution {
public static void main(final String[] args) {
final Solution solution = new Solution();
final int[] nums = new int[] { 2, 3, 1, 0, 2, 5, 3 };
System.out.println(solution.findRepeatNumber(nums));
System.out.println(solution.findRepeatNumber2(nums));
}
/**
* 方法一：遍历数组
*
* 遍历数组中的每个元素： * 将该元素加入集合中，判断是否加入成功 * 添加失败，则找到重复数字
*
* 时间复杂度 O(n) 空间复杂度 O(n)
*
* @param nums
* @return
*/
public int findRepeatNumber(final int[] nums) {
Set<Integer> set = new HashSet<>();
int repeat = -1;
for (final int num : nums) {
if (!set.add(num)) {
repeat = num;
break;
}
}
return repeat;
}
/**
* 方法二：原地置换
* 注意所有数字都在 0～n-1 的范围内
* @param nums
* @return
*/
public int findRepeatNumber2(final int[] nums) {
int len = nums.length;
int temp = 0;
for (int i = 0; i < len; i++) {
if (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
} else {
temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
}
return -1;
}
}
C++
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int len = nums.size();
int temp = 0;
for (int i = 0; i < len; ++i) {
if (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
} else {
temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
}
return -1;
}
};
int main() {
auto s = new Solution();
vector<int> v = {2, 3, 1, 0, 2, 5, 3};
cout << s->findRepeatNumber(v) << endl;
delete s;
}
Python
from __future__ import annotations
from typing import List
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
size = len(nums)
temp = 0
for index, value in enumerate(nums):
if value != index:
if value == nums[value]:
return value
else:
temp = value
value = nums[temp]
nums[temp] = temp
return -1
if __name__ == "__main__":
s = Solution()
print(s.findRepeatNumber([2, 3, 1, 0, 2, 5, 3]))
总结
最新文章
- SELECT CAST(GETDATE() AS VARCHAR(10)) 显示不同格式的原因
- Linux下怎么删除非空目录
- 深入浅出JMS（一）——JMS简介
- jsp_包含指令
- Windows环境下利用github快速配置git环境
- 如何使用setup.py文件
- 【Redis】配置redis主从复制
- memcahced 更新
- WinForm 实现登录，验证成功，关闭登录界面，显示主界面
- 例6.1：学生选课系统设计（界面设计、类图、数据库ER图）
- Android 使用 intent 实现简单登陆页面
- NYIST OJ 题目38 布线问题
- Python 逻辑行/物理行
- mysql建表---级联删除
- WPF自学入门（八）WPF窗体之间的交互
- JS 的骚操作
- jq里验证插件的自定义方法Jquery.validator.addMethod()示例
- win8.1安装win64_11gR2_database_2of2 【INS-13001]】环境不满足最低要求问题
- Java并发编程（六）-- 同步块
- Java中的异常 Exceptions