首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

    题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过数组长度的一半。这种方法的时间复杂度为O(n^2),在面试中,第一反应想到的方法往往不是最佳答案,下面我们来寻求更加高效的方式。 一个数出现的次数如果超过数组长度的一半,那么可以得出以下结论: 1.如果把超过数组长度一半的数整理在一起形成数组b,那么不管把b放在数组的什么位置,数组的中位数一定在b中。 2.个数超过数组长度一半的数最多只有一个。

    06

    LeetCode笔记:349. Intersection of Two Arrays

    这个问题思路倒是有的,不过一开始我的返回值没有做处理,导致一直报错,折腾一番后发现还是最初的想法比较好。 先说最初的想法错误的以为不行后尝试的简单方法,就是遍历第一个数组,对其中每个数字在第二个数组中找是否有,如果找到了,就放入结果数组中,当然结果数组因为要求每个数字都是唯一的,所以也要再检查一遍这个数字在结果数组中是否出现过,这个方法循环套循环,想来也是比较耗时的,虽然可以在找到交叉点数字后在第二个数组中去掉该数字做一点优化,但依然比较耗时。 现在回到最初的想法,先给两个数组分别排序后,同时从两个数组的第一个数字开始比较,同时各自设置一个标记,记录当前数组中比较到哪个位置了,如果哪个数组中的数字小一些,就将其标记往后移,再比较大一些的那个数字。如果发现比较的两个数字相等,则说明交叉了,就要考虑放到结果数组中了,放的时候要检查一下之前有没有放入过,但是因为放到结果数组中的数字一定也是有序的,所以只用比较和结果数组中上一个数字是不是相同就可以了,这样同样节省了时间,让后两个数组中的标记都往后移一位继续比较。这里移位的时候要注意一点,for循环如果是以一个数组的长度来当做结束判断条件的,那么在对另一个数组的标记做移位时每次都要判断是不是已经到最后一位了,否则会超出数组的,这里很容易忽略。 因为我们一开始创建结果数组时肯定是以其中一个数组的长度去创建的,但是最终返回时必须要处理一下,只能返回有数字的那部分长度,否则会报错。这些都是坑。 这个做法除了一开始的排序外,剩下的比较的复杂度因为边遍历边比较,只遍历了一次,还是同时遍历的,而且判断结果数组中是否重复时只用和上一位数字比较,所以只有O(n),还是比较快的,我做出来的时间也是3ms,挺快的。

    01
    领券