第3题-小美复原数组 - Problem Detail - CodeFun2000

1000ms

Difficulty: 4

所属公司 : 美团

时间 :2024年4月6日

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

题解

对数组 $b$ 和 $c$ 进行排序,因为前缀和数组是有序的。
通过前缀和的差分,还原出 $b$ 和 $c$ 代表的原始数组,记为 nums1 和 nums2 。
遍历 nums2 ,找到第一个不存在于 nums1 中的数 $x$ ,设其下标为 $i$ :

如果 $i=n-1$ ,说明x是原数组的最后一个数,直接将 $x$ 添加到 nums1末尾即可。

题目描述

小美有一个由 $n$ 个互不相等的正整数构成的数组a，但她一不小心把a弄丢了，他想要重新找到 $a$ 。

好在她并不是一无所有，她还记得以下有关 $a$ 的信息：