网站怎么自适应,遂宁网站优化,建站神器,茂名百度seo公司分享一道leetcode上的题#xff0c;当然#xff0c;居然不是放在刷题贴里来讲#xff0c;意味着分享的这道题不仅仅是教你怎么来解决#xff0c;更重要的是这道题引发出来的一些解题技巧或许可以用在其他地方#xff0c;下面我们来看看这道题的描述。 问题描述 给定一个未…分享一道leetcode上的题当然居然不是放在刷题贴里来讲意味着分享的这道题不仅仅是教你怎么来解决更重要的是这道题引发出来的一些解题技巧或许可以用在其他地方下面我们来看看这道题的描述。 问题描述 给定一个未排序的整数数组找出其中没有出现的最小的正整数。 示例 1:输入: [1,2,0]
输出: 3
示例 2:输入: [3,4,-1,1]
输出: 2
示例 3:输入: [7,8,9,11,12]
输出: 1
复制代码说明: 你的算法的时间复杂度应为O(n)并且只能使用常数级别的空间。 解答 这道题在 leetcode 的定位是困难级别或许你可以尝试自己做一下然后再来看我的解答下面面我一步步来分析秒杀的大佬请忽略..... 对于一道题如果不能第一时间想到最优方案时我觉得可以先不用那么严格可以先采用暴力的方法求解出来然后再来一步步优化。像这道题我想如果可以你要先用快速排序先把他们排序然后在再来求解的话那是相当容易的不过 O(nlogn) 的时间复杂度太高其实我们可以先牺牲下我们的空间复杂度让保证我们的时间复杂度为 O(n)之后再来慢慢优化我们的空间复杂度。 方法一采用集合 我们知道如果数组的长度为 n那么我们要找的目标数一定是出于 1~n1 之间的我们可以先把我们数组里的所有数映射到集合里然后我们从 1~n 开始遍历判断看看哪个数是没有在集合的如果不存在的话那么这个数便是我们要找的数了。如果 1~n 都存在那我们要找的数就是 n1 了。 不过这里需要注意的是在把数组里面的数存进集合的时候对于 小于 1 或者大于 n 的数我们是不需要存进集合里的因为他们不会对结果造成影响这也算是一种优化吧。光说还不行还得会写代码代码如下 public int firstMissingPositive(int[] nums) {SetInteger set new HashSet();int n nums.length;for (int i 0; i n; i) {if (nums[i] 1 nums[i] n) {set.add(nums[i]);}}for (int i 1; i n; i) {if (!set.contains(i)) {return i;}}return n 1;}
复制代码采用 bitmap 方法一的空间复杂度在最块的情况下是 O(n)不知道大家还记不记得位算法其实我们是可以利用位算法来继续优化我们的空间的如果不知道位算法的可以看我直接写的一篇文章 1、什么是bitmap算法。 2、自己用代码实现bitmap算法; 通过采用位算法我们我们把空间复杂度减少8倍即从 O(n) - O(n/32)但其实 O(n/32) 任然还算 O(n)不过在实际运行的时候它是确实能够让我们运行的更快的在 Java 中已经有自带的支持位算法的类了即 bitSet如果你没学过这个类我相信你也是能一眼看懂的代码如下 public int firstMissingPositive2(int[] nums) {BitSet bitSet new BitSet();int n nums.length;for (int i 0; i n; i) {if (nums[i] 1 nums[i] n) {bitSet.set(nums[i]);}}for (int i 1; i n; i) {if (!bitSet.get(i)) {return i;}}return n 1;}
复制代码方法3最终版本 如果这个数组是有序的那就好办了但是如果我们要把它进行排序的话又得需要 O(nlogn) 的时间复杂度那我们有没有啥办法把它进行排序然后时间复杂度又不需要那么高呢 答是可以刚才我们说过对于那些小于 1 或者大于 n 的数我们是其实是可以不理的居然我们我们需要处理的这些数他们都是处于 1~n 之间的那要你给这些处于 1~n 之间的数排序并且重复的元素我们也是可以忽略掉的记录一个就可以了那么你能不能在 O(n) 时间复杂度排序好呢 不知道大家是否还记得我之间写过的下标法 一些常用的算法技巧总结。 或者是否还记得计数排序计数排序其实就是下标法的一个应用了 不过学过计数排序的朋友可能都知道计数排序是需要我们开一个新的数组的不过我们这里不需要这道题我们可以这样做例如对于 nums[i]我们可以把它放到数组下标位 nums[i] - 1 的位置上这样子一处理的话所有 1nums[i]n 的数就都是是处于相对有序的位置了。注意我指的是相对也就是说对于 1-n 这些数而言其他 小于 1 或者大于 n 的我们不理的。例如对于这个数组 nums[] {4, 1, -1, 3, 7}。 让 nums[i] 放到数组下标为 nums[i-1]的位置并且对于那些 nums[i]0 或 nums n的数我们是可以不用理的所以过程如下从下标为 0 开始向右遍历 1、把 4 放在下标为 3 的位置为了不让下标为 3 的数丢失把下标为 3 的数与 4进行交换。 2、此时我们还不能向右移动来处下标为1的数因为我们当前位置的3还不是处于有序的位置还得继续处理所以把 3 与下标为 2 的数交换 3、当前位置额数为 -1不理它前进到下标为 1 的位置把 1 与下标为 0的数交换 4、当前位置额数为 -1不理它前进到下标为 2 的位置此时的 3 处于有序的位置不理它继续前进4也是处于有序的位置继续前进。 5、此时的 7 n不理它继续前进。 遍历完成此时那些处于 1~n的数都是处于有序的位置了对于那些小于1或者大于n的我们忽略它假装没看到就是了。 这里还有个要注意的地方就是 nums[i] 与下标为 nums[i]-1的数如果相等的话也是不需要交换的。 接下来我们再次从下标 0 到下标 n-1 遍历这个数组如果遇到 nums[i] ! i 1 的数那么这个时候我们就找到目标数了即 i 1。 好吧我觉得我讲的有点啰嗦了还一步步话题展现过程给你们看连我自己都感觉有点啰嗦了大佬勿喷哈。最后代码如下 public int firstMissingPositive(int[] nums) {if(nums null || nums.length 1)return 1;int n nums.length;for(int i 0; i n; i){// 这里还有个要注意的地方就是 nums[i] 与下标为 nums[i]-1的数如果相等的话// 也是不需要交换的。while(nums[i] 1 nums[i] n nums[i] ! i 1 nums[i] ! nums[nums[i]-1] ){// 和下标为 nums[i] - 1的数进行交换int tmp nums[i];nums[i] nums[tmp - 1];nums[tmp - 1] tmp;}}for(int i 0; i n; i){if(nums[i] ! i 1){return i 1;}}return n 1;}
复制代码这道题我觉得还是由挺多值得学习的地方的例如它通过这道原地交换的方法使指定范围内的数组有序了。 还有就是这种通过数组下标来解决问题的方法也是一种常用的技巧例如给你一副牌让你打乱顺序之后分发给4个人也是可以采用这种方法的详情可以看这道题什么是洗牌算法。 最后推广下我的公众号苦逼的码农公众号里面已经有100多篇原创文件也分享了很多实用工具海量视频资源、电子书资源关注自提。点击扫码关注哦。 戳我即可关注
