首页 > 7.22面试遇到的算法题(字节)
头像
celavie
编辑于 2020-07-23 19:00
+ 关注

7.22面试遇到的算法题(字节)

昨天参加了字节跳动的面试,然后面试官给了一道算法题,题目如下:
输出两个数组的交集输入:A=[1,4,2,3,5,6,7,3,5】,B=[3,4,2,3,4,6,7]
需要输出: 【4,2,3】【6,7】
因为做算法题的时间已经不多了,所以并没有和面试官讨论。但是对于这道题仍然有一些疑惑的地方,因此贴出来希望大家可以帮忙指正一下疑惑或者提出精彩的解题思路。
首先求数组的交集,如果是单纯求交集那么leetcode是有一道easy难度的题可以解决的(leetcode 349),而这道题的难点在于,需要将交集连续输出,如 [4,2,3]和[6,7]
我的思路是采取hash和滑动窗口和贪心来解决:
def intersection(a,b):
    ans=[]
    p=0
    while(p<len(a)):
      if a[p] in dic:
         start=p
         dis=float("-inf")
         for k in dic[a[p]]:
             index=p
             while(index<len(a) and k<len(b) and a[index]==b[k]):
                    index+=1
                    k+=1
             dis=max(index-start,dis)
         p=start+dis
         ans.append(a[start:start+dis])
      else:
         p+=1
    return ans
a=list(map(lambda x:int(x),input().split()))
b=list(map(lambda x:int(x),input().split()))
intersection(a,b)
output:
[[4, 2, 3], [6, 7], [3]]
这里输出明显是有问题多了`一个3,所以我对这个数组交集的定义的理解可能有偏差如果说是因为【4,2,3】已经包含了3是不意味着这个数组交集的本质也是看单个数组元素呢?
也不确定是不是自己把问题想复杂了比如【1,2,3,1,2】与【1,2,1,2,3】交集应该是怎样的呢?希望有思路的同学可以不吝赐教,谢谢。

更多模拟面试

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐