当前位置:网站首页>寻找重复数[抽象二分/快慢指针/二进制枚举]
寻找重复数[抽象二分/快慢指针/二进制枚举]
2022-07-02 02:52:00 【REN_林森】
前言
保持有序对二分/抽象二分的敏感性;保持环问题/死循环对快慢指针的敏感性。
一、寻找重复数
二、抽象二分/快慢指针/二进制枚举
package everyday.doublePoint;
// 寻找重复数
public class FindDuplicate {
/* 将自己放到自己的位置上,如果已经被占了,说明重复。 这个修改了数组,双指针,O(n),O(1) */
public int findDuplicate(int[] nums) {
for (int i = 0; i < nums.length; ) {
if (nums[i] - 1 != i) {
if (nums[nums[i] - 1] == nums[i]) return nums[i];
// 交换位置
int t = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = t;
} else ++i;
}
return 1;
}
/* 题目要求,是不能修改数组的。所以要么双循环O(N^2^)/O(1),要么hash记录O(N)/O(N). 而二分法可以完成不修改数组,O(NlogN)/O(1) 保持有序对二分法的敏感性,看到1-n联想到二分法,抽象二分。(其实二分和快慢指针都属于双指针类型) 数组中的元素是1-n,加上重复元素,一共就是n+1个元素,重复元素为1-n中的其中一个元素。 将区间[1,n]划分为[1,mid]/[mid,n],记录数组中小于等于mid的元素个数cnt,如果出现 cnt > mid的情况,说明重复元素小于等于mid。 */
public int findDuplicate2(int[] nums) {
int low = 1, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low >>> 1);
// 求小于等于mid的元素个数。
int cnt = 0;
for (int num : nums) cnt += num > mid ? 0 : 1;
// 抽象判定规则,若小于等于mid的元素超过了mid个,则重复元素x <= mid
if (cnt > mid) high = mid;
else low = mid + 1;
}
return low;
}
/* 元素属于1-n,共n + 1个元素,若每次都取nums[nums[i]]表示:nums[i]走到下一跳nums[nums[i]]。 在index:1-n的闭环内跳,当碰到后面相同的元素时,又会跳到同一个地方继续前进,再次来到第2个重复的地方,又跳到前面同一个地方。 保持环/死循环对快慢指针的敏感性。 但是这里不仅仅单纯判定环,下一个关键问题是如何用快慢指针确定环的入口? 解答见代码中的注释。 */
public int findDuplicate3(int[] nums) {
int fast = nums[nums[0]], slow = nums[0];
while (fast != slow) {
fast = nums[nums[fast]];// 在闭环内走两步。
slow = nums[slow];// 在闭环内走一步。
}
// 在快指针是慢指针2倍的背景下,设起点到环口的长度是a,慢指针在环内走了b和快指针相遇。
// 相遇时,慢指针走了a+b步,快指针走了2(a+b)步,可以理解为快指针走了a+b步,到达相遇地点,而剩下的a+b步则绕环走了k圈。
// 设环长L,则a+b = kL -> a = kL - b = (k - 1)L + (L - b).
// 设从相遇地点走c步到入口,则a=(k-1)L+c,所以从起点走a步到入口,快指针刚好走了k-1圈(回到相遇地点) & c步到达入口
// 注:可证明:K>=1,即快指针至少走了一圈赶上了慢指针。
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
/* 二进制枚举法。 思考角度,按位展开,如果能找重复元素每一位是0还是1,就能得到重复元素。 设第i位,nums所有数展开为1的数是x,把1-n所有数展开为1的数是y,如果x > y,则表示重复元素第i位为1. */
public int findDuplicate4(int[] nums) {
int n = nums.length, ans = 0;
int bit_max = 31;
while (((n - 1) >> bit_max) == 0) {
bit_max -= 1;
}
for (int bit = 0; bit <= bit_max; ++bit) {
int x = 0, y = 0;
for (int i = 0; i < n; ++i) {
if ((nums[i] & (1 << bit)) != 0) {
x += 1;
}
if (i >= 1 && ((i & (1 << bit)) != 0)) {
y += 1;
}
}
if (x > y) {
ans |= 1 << bit;
}
}
return ans;
/* 作者:LeetCode-Solution 链接:https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 */
}
}
总结
1)保持有序对二分/抽象二分的敏感性;
2)保持环问题/死循环对快慢指针的敏感性。
参考文献
[1] LeetCode 寻找重复数
[2] LeetCode 官方题解
边栏推荐
- 【带你学c带你飞】1day 第2章 (练习2.2 求华氏温度 100°F 对应的摄氏温度
- 创业了...
- How to develop digital collections? How to develop your own digital collections
- [question 008: what is UV in unity?]
- 旋转框目标检测mmrotate v0.3.1 学习模型
- 2022-2028 global soft capsule manufacturing machine industry research and trend analysis report
- Query word weight, search word weight calculation
- Systemserver service and servicemanager service analysis
- 结婚后
- MongoDB非關系型數據庫
猜你喜欢
Vsocde has cli every time it is opened js
Which brand of running headphones is good? How many professional running headphones are recommended
【liuyubobobo-玩转Leetcode算法面试】【00】课程概述
Batch detect whether there is CDN in URL - high accuracy
Soul app released the annual report on generation Z behavior: nearly 20% of young people love shopping in the vegetable market
批量检测url是否存在cdn—高准确率
超图iServer rest服务之feature查询
Redis cluster
How to develop digital collections? How to develop your own digital collections
小米青年工程师,本来只是去打个酱油
随机推荐
Actual battle of financial risk control - under Feature Engineering
【带你学c带你飞】day 5 第2章 用C语言编写程序(习题2)
Realize the code scanning function of a custom layout
STM32__ 05 - PWM controlled DC motor
Use usedeferredvalue for asynchronous rendering
2022低压电工考试题模拟考试题库模拟考试平台操作
Yyds dry goods inventory accelerating vacuum in PG
[learn C and fly] 3day Chapter 2 program in C language (exercise 2.3 calculate piecewise functions)
QT使用sqllite
QT implementation interface jump
Jvm-01 (phased learning)
C write TXT file
[opencv] - comprehensive examples of five image filters
Special symbols in SAP ui5 data binding syntax, and detailed explanation of absolute binding and relative binding concepts
小米青年工程师,本来只是去打个酱油
[staff] restore mark (Introduction to the use of restore mark | example analysis of Metaphone mark and restore mark)
2022-2028 global aluminum beverage can coating industry research and trend analysis report
QT uses sqllite
2022-2028 global encryption software industry research and trend analysis report
CoordinatorLayout + TabLayout + ViewPager2(里面再嵌套一个RecyclerView),RecyclerView的滑动冲突解决