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

首页课程实战体系课手记专栏慕课教程

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

来源：4-2 map的使用 Intersection of Two Arrays II

软件工程小白菜

2019-04-09

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

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

请老师指点，多谢！

写回答

1回答

liuyubobobo

liuyubobobo

2019-04-09

已采纳

不使用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

3

liuyubobobo

回复

不考过程序员不改名字

已更新：）

2021-07-01

共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

377号组合数问题

回答 2

老师，我想问一下如何实现一个数组转化为二叉树，非完全二叉树,如[1,2,null,null,4,5]这种

回答 2

39. Combination Sum这个程序为什么可以简单的通过参数i的传递就处理了重复的组合？？

回答 1

两个有序数组合并为一个有序数组，如果这两个数组不同为升序/降序呢？

回答 1

关于80号问题

回答 1

打开慕课网App查看更多内容