LC 350题关于有序数组的实现

Question

波波老师您好，我思考了您留下的问题。并且实现了349题有序数组的版本，在没有使用Set的情况下，时间复杂度也达到了O(nlogm)或者O(mlogn)。

但是在350题，却发现不用Map有些困难，因为如果单纯使用二分查找法，无法记录一个元素在两个数组中出现的频次。所以请问在二分查找过程中，是否查找到一个元素后，需要对这个元素在数组中进行删除元素的操作？如果对数组进行删除元素操作，则需要对每一个元素进行位移，时间复杂度岂不是变为O(n * logm * m) 或者 O(m * logn * n) ?

请老师指点，多谢！

Answer 1

liuyubobobo 2019-04-09 13:50:03

不使用map的方式是排序以后使用双指针技术：）

可以参考我的代码，看是否能理解？

C++版：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0350-Intersection-of-Two-Arrays-II/cpp-0350/main3.cpp 

Java版：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0350-Intersection-of-Two-Arrays-II/java-0350/src/Solution2.java 

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！

• 不考过程序员不改名字 #2

  老师能再发下java代码的连接嘛，之前的链接挂掉了

• liuyubobobo 回复 不考过程序员不改名字 #3

  已更新：）