September 2023Monthly Archives

原题：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 示例 ： 输入：nums = [2,2,1,1,1,2,2] 输出：2 思路一 首先想到用哈希表记录每个元素出现的次数，然后遍历哈希表，次数最多的值即为答案，比较简单，在此就不放代码了 复杂度：需要遍历一次数组，一次哈希表，且需要哈希表存储最多 n/2 + 1 个元素，故时间复杂度O(n)，空间复杂度O(n) 思路二 上面的思路不满足题目进阶要求中的空间复杂度O(1)，仔细想想自己忽略了一个条件——多数元素出现次数大于 n/2。 要利用这个条件需要一个数学公式，令数组总长度为a，多数元素个数为b，在题目所给条件下有(证明在下方)： \frac{b}{a} > \frac{1}{2}，\frac{b – 1}{a – 2} > \frac{1}{2} 考虑每次从数组中取出两个不同的元素，由于多数元素出现次数大于 n/2，由上面的公式可知，在最坏情况，即每次都取出多数元素的情况下，取出两个不同元素后，数组的多数元素仍然不变 故可将上述思路转换为：将第一个元素设为候选多数元素，遍历数组并计数，若遇到不同元素，则将当前元素的计数减一(相当于取出两个不同元素)，反之加一，元素的计数为0时将候选元素替换为下一个元素，最终剩下的候选元素即为我们需要的结果 代码： var majorityElement = function(nums) { let… Continue Reading 算法题记录——多数元素

原题：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 示例： 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 思路 看到示例第一时间想到用双指针解决，关键在于何时移动左指针或右指针，并更新结果的最大值 记左指针为lp，右指针rp，记[lp, rp]区间能盛水的值为 y，由短板效应易知 *y = min(height[lp], height[rp]) (rp – lp)** 初始时令lp = 0，rp = n – 1，假设某状态下height[lp] < height[rp]，考虑此时如何移动指针 若将lp右移，则当 height[lp + 1] > height[lp]… Continue Reading 算法题记录——盛最多水的容器