移动网站建设可信赖,wordpress支持HTML么,贵阳做网站好的公司有哪些,数据库网站制作蝶恋花-王国维 阅尽天涯离别苦#xff0c; 不道归来#xff0c;零落花如许。 花底相看无一语#xff0c;绿窗春与天俱莫。 待把相思灯下诉#xff0c; 一缕新欢#xff0c;旧恨千千缕。 最是人间留不住#xff0c;朱颜辞镜花辞树。 目录
题目描述#xff1a;
思路分析… 蝶恋花-王国维 阅尽天涯离别苦 不道归来零落花如许。 花底相看无一语绿窗春与天俱莫。 待把相思灯下诉 一缕新欢旧恨千千缕。 最是人间留不住朱颜辞镜花辞树。 目录
题目描述
思路分析
方法及时间复杂度
法一 排序数组(暴力解法)
法二 哈希表
法三 二分查找(经典解法)
法四 快慢指针
法五 二进制(烧脑解法)
个人总结 题目描述 287. 寻找重复数 - 力扣LeetCode 思路分析
在一个数组中查找唯一重复的元素可以用很多解法立马想到的便是哈希表。将数组元素插入哈希表然后查找哈希表找到了就返回该数 方法及时间复杂度
法一 排序数组(暴力解法)
将数组进行排序这样重复的元素一定相邻然后遍历排序后的数组就行。代码如下 int cmp(const void*a,const void*b){return *(int*)a-*(int*)b;
}
int findDuplicate(int* nums, int numsSize) {qsort(nums,numsSize,sizeof(int),cmp);for(int i1;inumsSize;i){if(nums[i]nums[i-1]){return nums[i];}}return -1;
}
时间复杂度O(nlogn) 排序的时间nlogn
空间复杂度O(1) 法二 哈希表
利用哈希表查找哈希表中存在的元素即数组重复的元素。可以使用c容器的哈希集合unordered_set这里用c语言数组模拟了一个哈希表。代码如下
int findDuplicate(int* nums, int numsSize) {int hash[100001]{0};//初始化哈希表所有元素为0for(int i0;inumsSize;i){if(hash[nums[i]]){//查找哈希表中是否存在该元素return nums[i];}hash[nums[i]];}return -1;
}
时间复杂度O(n)
空间复杂度O(n) 空间换时间了属于是 法三 二分查找(经典解法)
用此方法前先弄清楚什么是鸽巢原理。
鸽巢原理也称为抽屉原理是一个基本的数学原理这个原理的经典解释是就像将若干只鸽子放在若干个鸽巢中一样如果鸽子的数量大于鸽巢的数量那么至少有一个鸽巢中放了两只鸽子。 这里抽象成二分查找那个装有两只鸽子的鸽巢 二分查找的区间很明显就是【1n-1】n为数组长度。查找中点mid先猜一个鸽巢遍历数组并记录mid的数如果mid的数大于mid说明这个有着两只鸽子的鸽巢在左区间反之如果mid的数小于等于mid就在右区间。直到leftright时这个鸽巢就是有着两只鸽子的鸽巢。
代码如下
int findDuplicate(int* nums, int numsSize) {int left1,rightnumsSize-1;while(leftright){int mid(leftright)1;int cnt0;for(int i0;inumsSize;i){if(nums[i]mid){cnt;}}if(cntmid){rightmid;}else{leftmid1;}}return left;
}
时间复杂度O(nlogn) 二分查找时间复杂度 logn,然后每次查找都要遍历数组O(n)
空间复杂度O(1) 法四 快慢指针
下标向值引一条边值向下标引一条边从0开始沿着箭头走逐渐就会进入一个环环的入口就是重复的元素。 类似于环形链表定义快指针fast慢指针slow。慢指针每次走一步快指针每次走两步快指针会在环里追上慢指针然后让快指针从0开始走快慢指针同时走一步相逢时就是环的入口即重复元素。
代码如下
int findDuplicate(int* nums, int numsSize) {int slow0,fast0;do{slownums[slow];fastnums[nums[fast]];}while(slow!fast);fast0;while(slow!fast){slownums[slow];fastnums[fast];}return slow;
}
时间复杂度O(n)
空间复杂度O(1) 法五 二进制(烧脑解法)
可以使用二进制位运算来解决此题。我们可以将数组 nums 中的每一个数字用二进制来表示最多只需要 log(n) 位其中 n 是数组 nums 的长度。
对于每一位 i我们可以计算在此位上所有数字出现的次数之和。如果某一位上的出现次数之和大于 2说明出现了重复的数字。
具体做法如下
对于二进制的第 i 位计算所有数字的二进制表示中第 i 位上出现 1 的次数之和可以使用位运算和移位操作进行统计。如果第 i 位上出现 1 的次数之和大于 2说明重复数字在此位上的值为 1否则为 0。将所有位上确定的二进制位还原成对应的十进制数字即为重复的数字。
代码如下
int findDuplicate(int* nums, int n) {int ans 0;// 确定二进制下最高位是多少int bit_max 31;while (!((n - 1) bit_max)) {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)) {x 1;}if (i 1 (i (1 bit))) {y 1;}}if (x y) {ans | 1 bit;}}return ans;
}
时间复杂度O(nlogn) 枚举二进制数的位数个数O(logn)
空间复杂度O(1) 个人总结
二分查找的算法其实还可以优化。 有位大师曾经说过完成比完美更重要。
