两个数组中寻找相同元素的算法(待补充)

假设数组A有n个元素,数组B有n个元素,两个数组中寻找相同元素。

最简单直观的算法是 两个for循环遍历数组元素,但是此时的算法复杂度是O(n2),效率非常低。

发散思维利用数组C下标来标记一个数组元素,用C[i]中的元素i出现次数,然后对于数组A中的元素,查找对应的C[i]中元素值是不是为0;此时算法时间消耗在:

     1,将B映射到C中,需要时间O(n);

     2,查找相同元素时,需要遍历A数组,需要时间O(n);

这个情况下,总的时间复杂度就是O(n+n);

这个算法适用于元素不是特别分散的情况下,否则C需要比较大的空间。

典型的“以空间换时间”;

解决该B数组元素分散的方法可以利用hash表的方法,设计一个合理的函数,将B中分散的元素紧凑起来;

原文地址:https://www.cnblogs.com/HuaiNianCiSheng/p/3094487.html