1.存在重复元素（217 - 易）
题目描述：给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 :
输入: [1,2,3,1]
输出: true
思路：
-
本题可以先排序再遍历数组，简单。
-
也可以利用HashSet去重判断，依次计入集合。
代码实现：hashset
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
return set.size() < nums.length;
}
2.剑指 Offer 03. 数组中重复的数字
题目描述：找出数组中重复的数字（含有多个重复元素）。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 :
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
思路：
-
使用hashset，当元素王集合中加入失败
if (!set.add(num))，即存在重复元素，返回即可（返回任意重复元素）。 -
原地置换（快慢指针）：根据题目元素都小于长度n，可以让 位置i 的地方放元素i（有重复数字，索引和值是一对多映射）。
- 如果位置i的元素不是i的话，那么我们就把i元素放到它应该在的位置，即 nums[i] 和nums[nums[i]]的元素交换（即元素nums[i]应该放在下标nums[i]），这样就把原来在nums[i]位置的元素正确归位了。
- 如果发现 要把 nums[i]位置元素正确归位的时候，发现nums[i]（这个nums[i]是下标）那个位置上的元素和要归位的元素已经一样了，此时一定nums[i] == nums[nums[i]]，说明就重复了
- 值域的二分查找：数组元素值介于 0～n-1，且至少存在一个元素是重复的。可以对值域进行二分查找，统计nums数组中元素介于0mid的数量，如果这个数量大于mid值，重复元素肯定在0m之间。
ps：二分查找没有ac，请教大佬指点！
代码实现：hashset实现：额外空间复杂度O(N)，不修改原始数据。
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int repeat = -1;
for (int num : nums) {
// 集合中已经存在该元素
if (!set.add(num)) {
repeat = num;
break;
}
}
return repeat;
}
快慢指针（原地置换）：不使用额外空间，原地查找，时间复杂度O(N)，但修改了原始数据。
public int findRepeatNumber(int[] nums) {
int tmp;
for(int i = 0; i < nums.length; i++){
while (nums[i] != i){
if(nums[i] == nums[nums[i]]){
return nums[i];
}
// 将元素nums[i]归位（放到下标为nums[i]位置）
tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return -1;
}
3.寻找重复数（287 - 中）
题目描述：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
示例 :
输入：nums = [1,3,4,2,2]
输出：2
思路：
-
使用hashset，当元素王集合中加入失败
if (!set.add(num))，即存在重复元素，返回即可（返回任意重复元素）。 - 快慢指针（最优解），因为元素介于1~n，且只存在一个重复值，所以可以看成链表找环的入口，使用快慢指针查找，快指针一次跳两步（不会出现数组越界）。
- 二分查找：虽然数组无序，但是值域1~n，可以在值域上进行二分查找。
代码实现：
hashset实现：额外空间复杂度O(N)，不修改原始数据。
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) return num;
set.add(num);
}
return -1;
}
快慢指针：不使用额外空间，原地查找，时间复杂度O(N)，但修改了原始数据。
public int findDuplicate(int[] nums) {
int l1 = 0, l2 = 0;
while (true) {
l1 = nums[l1];
l2 = nums[nums[l2]];
if (l1 == l2) break;
}
l2 = 0;
while (l1 != l2) {
l1 = nums[l1];
l2 = nums[l2];
}
return l1;
}
值域的二分查找：时间O(NlongN)，额外空间复杂度O(1)，不修改原数据。
public int findDuplicate(int[] nums) {
int l = 1, r = nums.length - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
cnt++; //记录小于等于mid元素的个数
}
}
if (cnt > mid) { //重复值在左区域，mid取大了
r = mid;
} else {
l = mid + 1; //重复值在右区域，mid取小了
}
}
return l;
}
4.补充：快乐数（202 - 易）
题目描述：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 :
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路：快慢指针，每个数字都会根据 各位平方和 指向另一个数字，从任意数字开始进行 各位平方和 的迭代操作，就相当于在链表上游走。如果快指针找到则提前退出。如果快慢指针相遇，那么必定出现循环（存在环，死循环），需要判断这个循环值是不是1。
代码实现：
public int squareSum(int n) {
int sum = 0;
while(n > 0){
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
public boolean isHappy(int n) {
int slow = n, fast = squareSum(n);
while (fast != 1 && slow != fast){
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
}
return fast == 1;
}
5.删除有序数组中的重复项（26 - 易）
题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 :
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
思路：快慢指针，快指针遍历数组，慢指针记录不重复的元素（遇到与慢指针元素不同，将快指针指向元素覆盖慢指针指向元素），最后返回慢指针下标 + 1，即为删除后数组长度。
代码实现：快慢指针，不使用额外空间，原地查找，时间复杂度O(N)。
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
6.删除有序数组中的重复项II（80 - 中）
题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 :
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
思路：快慢指针，快指针遍历数组，慢指针记录不重复的元素，注意：这里快指针指向元素依次比较元素nums[slow - max + 1]，即上一轮已经覆盖完成的两个元素，这里max需要返回元素的最多重复数。
代码实现：快慢指针，不使用额外空间，原地查找，时间复杂度O(N)。
public int removeDuplicates(int[] nums) {
int slow = 1;
int max = 2; // 返回元素的最多重复次数
for (int fast = 2; fast < nums.length; fast++) {
if (nums[slow - max + 1] != nums[fast]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
网友评论