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

计算机萌新的成长历程——初识C语言13

怎么去理解数组的定义呢?数组就好比咱们养家畜、种果树一样,我现在圈了一块地,这块地是干嘛用的我还不清楚,有一天我放了一群小猪仔进去,那这块地我就叫它猪圈了,因为这块地里面全部都是小猪仔;我放了一群小鸡仔进去,那这里就叫鸡舍了,因为这块地里面全部都是小鸡仔;我种了很多棵苹果树进去,那这块地我就叫它苹果园了,因为里面全部都是苹果树……这里的不管是小猪也好,小鸡也好还是苹果树也好,都是这块地里的元素,这些元素聚集在一起就叫做集合,这块地不管是猪圈也好、鸡舍也好还是苹果园也好,它们就是数组。它叫猪圈时,里面的元素都是小猪;它叫鸡舍时里面的元素都是小鸡;它叫苹果园时里面的元素都是苹果树……我相信看到这里,大家应该都能明白数组的定义了。

04

LeetCode笔记:349. Intersection of Two Arrays

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

01
领券