forUsAll oa

今早做了forUsAll的oa题 两道题 贡献给地里的小伙伴

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问第二题的思路

BabyBabyXuan 发表于 2018-3-2 08:33
不 这三个数组没排序 就是举个例子哈： A[53, 28, 56, 20]  B[72, 32, 56, 48] C[12, 45, 90, 78]
假设 ...

那这题感觉可以先把这3个数组排序然后用3 pointers的做法，每个pointers一开始都指向每个array 的第一个elements，然后移动pointerb从b中找到第一个比A[pointa]大的，然后用pointerc从c中找到第一个比b[pointB]大的element，然后计算下有多少种可能，以此类推，应该可以吧～

kate8528577 发表于 2018-3-3 05:43
先是sort就nlogn了，然后先选第一个字母的那排，选了一个时候选下一排，二分法找到比他大的，然后第三排 ...

你就把原数组全部sort完，需要3nlogn.然后用pointer从做到右扫，不需要2pointer，这个时间复杂度是O(3n)。你虽然是nestedloop但是你的pointer在下一层for loop的时候没有从0开始，意思就是每个array最只要扫描1遍。

补充内容 (2018-3-3 09:34):
我的意思是：你就把原数组全部sort完，这一步需要3nlogn.然后用pointer从左到右扫，这个时间复杂度是O(3n)。虽然看上去是有nestedloop但pointer在一层for loop的时候没有从0开始，意思是每个array最多只要扫1遍

请问第二题有时间和复杂度的限制么。感谢。

补充内容 (2018-3-2 07:19):
时间和空间复杂度，sorry说错了刚才｀

liu.haonan 发表于 2018-3-2 07:18
请问第二题有时间和复杂度的限制么。感谢。

补充内容 (2018-3-2 07:19):

时间复杂度是O（nlogn）
空间复杂度是O(n)

tongyuze 发表于 2018-2-25 07:44
请问第二题的思路

我没做出来。。。

BabyBabyXuan 发表于 2018-3-2 07:47
时间复杂度是O（nlogn）
空间复杂度是O(n)

感谢楼主回复哈，还有个疑问，请问那这3个数组之前是已经排好序的了么？

liu.haonan 发表于 2018-3-2 08:24
感谢楼主回复哈，还有个疑问，请问那这3个数组之前是已经排好序的了么？

不 这三个数组没排序 就是举个例子哈： A[53, 28, 56, 20]  B[72, 32, 56, 48] C[12, 45, 90, 78]
假设你在A中选了56 B中只能选72（严格递增） C中可以选78或者90；
都是从A开始，B C中再各选一个数组成一个严格递增的集合 求满足条件的集合的个数

liu.haonan 发表于 2018-3-2 08:46
那这题感觉可以先把这3个数组排序然后用3 pointers的做法，每个pointers一开始都指向每个array 的第一个e ...

我觉得你的方法应该挺好的~

liu.haonan 发表于 2018-3-2 08:46
那这题感觉可以先把这3个数组排序然后用3 pointers的做法，每个pointers一开始都指向每个array 的第一个e ...

这样的话应该是3*n*logn