企业官网建设流程全解析

建设工程消防备案凭证网站,网站开发模板用什么,网站怎么做双机房切换,wordpress文章图片自适应题目难度: 简单 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品…题目难度: 简单原题链接今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号算法精选里回复剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~题目描述仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。示例 1输入stock [6, 1, 3, 1, 1, 1]输出1提示1 stock.length 50000给定数组为非空数组且存在结果数字题目思考如何不使用额外空间?如果题目不保证一定存在多数元素又该怎么办?解决方案思路一个最简单的思路是用一个计数字典存每个数字的出现次数, 找最大的那个即可, 但这需要额外的空间, 不是面试官心目中的理想答案重新分析题目, 某个数字出现超过一半, 那意味着其他数字的数目之和都小于它, 如果我们将这些不同数字进行两两抵消, 那么最后剩余的那个数字一定是超过一半的那个数字, 这就引出了下面的思路:维护一个当前候选者, 以及当前它的计数, 初始化就是数组头一个数字, 计数为 1从第二个数字开始遍历数组, 如果当前数字等于候选者, 那么计数值加 1, 否则就减 1 表示抵消了一个数字如果此时计数小于 0 的话, 就说明之前的候选者这个时候要被淘汰了, 因为它已经被抵消光了. 所以就重新选择当前的数字作为新的候选者, 同时重置计数值为 1.这样最后剩余的那个候选者一定是最终结果, 因为此题的前提是一定存在这样的数字当然, 如果题目不保证一定存在多数元素, 那么我们在得到最终候选者之后, 需要重新遍历一遍数组并累加其计数, 确保其计数超过一半, 不然的话就说明整个数组没有多数元素. 例如数组[1,2,3], 利用此方法得到的最终候选者为 3, 但它并不是多数元素, 只是恰好最后一个被选出来的候选者而已.复杂度时间复杂度O(N)只需要遍历数组一遍空间复杂度O(1)只使用了几个变量代码classSolution:definventoryManagement(self,stock:List[int])-int:# 初始化候选者和计数resstock[0]cnt1forxinstock[1:]:ifxres:# 当前元素等于候选者, 计数值1cnt1else:# 否则计数值-1cnt-1ifcnt0:# 如果计数值小于0的话, 就说明之前保存的候选者现在被淘汰了, 将当前元素变为新的候选者, 并重置计数值为1resx cnt1returnres大家可以在下面这些地方找到我~我的 GitHub我的 Leetcode我的 CSDN我的知乎专栏我的头条号我的牛客网博客我的公众号: 算法精选, 欢迎大家扫码关注~