给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。其中
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
例子
**输入: **nums1 = [4,1,2], nums2 = [1,3,4,2].
**输出: **[-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
**输出: **[3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
解题思路
1.哈希法
题意稍微解释下, 其实就是依次遍历数组1, 在数组2中找到数组1对应元素后面最大的1个, 没有返回-1
例子
nums1 = [4,1,2], nums2 = [1,3,4,2]
-
4, 在num2中4之后只有2,2比4小, 返回-1 -
1, 在num2中1之后有3, 4, 2, 取第一个最大3, 返回3 -
2, 在num2中2之后无元素, 返回-1
返回结果 [-1, 3, -1]
因为数组nums1和nums2没有重复元素, 并且nums1是nums2的子集, 那么用哈希法处理此题是一个相对好理解方法
遍历num2, 以每一项i做key, 以i之后第一个大于i的元素做value, 没有则value为-1, 则有
代码
未翻译版
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var res = [Int](), dic = [Int:Int]()
for i in 0..<nums2.count {
for j in i+1..<nums2.count {
if nums2[j] > nums2[i] {
dic[nums2[i]] = nums2[j]
break
}
}
// 下面if 加不加都行
//if dic.count < i + 1 {
// dic[nums2[i]] = -1
//}
}
for i in 0..<nums1.count {
res.append(dic[nums1[i]] ?? -1)
}
return res
}
翻译版
func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
// 定义结果res, 哈希表dic
var res = [Int](), dic = [Int:Int]()
// 遍历nums2中每一个元素nums2[i]
for i in 0..<nums2.count {
// 遍历i之后, 每一个元素
for j in i+1..<nums2.count {
// 找到后面第一个大于nums2[i]元素, 形成key-value
if nums2[j] > nums2[i] {
dic[nums2[i]] = nums2[j]
break
}
}
// 没有value - 1, 下面if 加不加都行
//if dic.count < i + 1 {
// dic[nums2[i]] = -1
//}
}
// 遍历num1, 依次添加数组
for i in 0..<nums1.count {
res.append(dic[nums1[i]] ?? -1)
}
return res
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
