Tiktok Intern OA

Sean2018 发表于 2022-10-5 08:23
第一道coding题请问是哪种方法过不了测试呀
还有时间复杂度是多少

第一题O(nlogn)会被卡，今天朋友线性复杂度也被卡了

非常喜欢楼主怒怼OA整活这种语气 爱了爱了 怒给加米！

tiany7 发表于 2022-10-04 18:22:36
前面两道选择题，都很简单，没啥问题
算法第一题，给出一个序列a和序列b，问能不能通过给序列a的一部分或者全部元素 + 1，让a成为b的一个permutation
都2202年了，还有人把数组以st

哇谢谢楼主

tiany7 发表于 2022-10-4 21:23
第一题O(nlogn)会被卡，今天朋友线性复杂度也被卡了

这题还能线性复杂度吗，不sort感觉没有办法做呀

Sean2018 发表于 2022-10-4 23:48
这题还能线性复杂度吗，不sort感觉没有办法做呀

我觉得Python sort会好很多

BruceTan02 发表于 2022-10-5 00:09
我觉得Python sort会好很多

我python写不太溜🙃

Sean2018 发表于 2022-10-4 21:48
这题还能线性复杂度吗，不sort感觉没有办法做呀

我用了2个map分别存对应数字的个数，然后从listA拿数字 ai 比较mapA和mapB里 ai 和 ai+1 对应的个数。这样时间复杂度是O(n)的。

反倒是之前看的sort的做法“先sort 了一下a, b list, 然后scan 从头到尾， 如果a[i] != b[i] and a[i]+1!=b[i], 就return false”。我感觉这个做法是对的，然而写出来有1/3的testcase过不了 不知道哪写错了。。

用的java，两种方法都没出现TLE

abwwqqyy 发表于 2022-10-6 12:29
我用了2个map分别存对应数字的个数，然后从listA拿数字 ai 比较mapA和mapB里 ai 和 ai+1 对应的个数。这 ...

你答案错了肯定就不会超时。oj的测试黑盒是遇到答案不对的即刻退出，不会等跑完的

Sean2018 发表于 2022-10-5 11:48
这题还能线性复杂度吗，不sort感觉没有办法做呀

可以的啊，你开个大数组，把所有负数 + 1e6提正就行了，所有数字装进桶，自然有序