寻找三个有序数组的共同最小元素_查找多个有序数组的最小重复元素

作者：weixin_40725706 | 2024-06-07 11:58:32

踩

查找多个有序数组的最小重复元素

题目：

有3个数组x[]、y[]与z[]，各有x、y与z个元素，而且三者都已经从小到大依序排列。编写一个程序，找出值最小的共同元素（也就是同时在3个数组中出现，并且值最小的元素)；但若没有共同元素，请显示合适的信息。

解法：

对于这个题目，最容易想到的方法即依次扫描数组x和数组y，每当x[i] == y[i]时，则在数组z中搜索x[i]是否同样存在于数组z中。假设数组x,y,z的长度分别为m,n,p。则该算法的复杂度为O(min(m,n)) + k*O(lgp).其中k表示数组x和数组y中相同元素的个数。那么这个算法最坏情况下需要运行O(min(m,n)*lg(p)).当然，我们可以根据m，n，p的大小关系，来决定哪个数组用于搜索，哪两个数组用于比较求相等的值，使得最终的复杂度最小。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/685298