文章目录

• 1. 问题描述
• 2. 问题示例
• 3. 代码实现
• 4. 运行结果
• 总结

1. 问题描述

两个不重复的数组 nums1和nums2,nums1是nums2的子集，在nums2的相应位置找到nums1所有元素的下一个更大数字。
nums1中的数字x的下一个更大数字是nums2中x右边第一个更大的数字。不存在则输出-1。nums1和nums2都是唯一的,nums1和nums2的长度不超过1000

2. 问题示例

输入：nums1 = [4,1,2] nums2 = [1,3,4,2] 输出:[-1,3,-1]
输入：nums1 = [2,4] nums2 = [1,2,3,4] 输出:[3,-1]
输入：nums1 = [2,8,7,3,11,4] nums2 = [2,10,8,0,7,1,3,11,9,4] 输出:[10,11,11,11,-1,-1]

3. 代码实现

class Solution:# 参数nums1：整数数组# 参数nums2：整数数组# 返回整数数组def nextGreatElement(self,nums1,nums2):answer =  {}stack = []for x in nums2:while stack and stack[-1] < x: # 第一次stack为空不会执行while循环 会先加入到列表stackanswer[stack[-1]] = x      # 加入字典del stack[-1]              stack.append(x)for x in stack:answer[x] = -1return [answer[x] for x in nums1] # 通过键获得值 并返回列表
"""
方法二：为nums2维护一个字典，key为当前元素，value为该元素的下一个比其大的值
设置一个递减栈，当遇到更大的元素时，把栈里比他小的元素都放到字典中
查找时只需要在字典中找。时间复杂度O(n+m) 空间复杂度O(m)
"""# 主函数
if __name__ == '__main__':s = Solution()nums1 = list(map(int,input('请输入以空格为分割的字符串数字：').split()))#①见总结nums2 = list(map(int,input('请输入以空格为分割的字符串数字：').split()))print('输入nums1=',nums1,'      ','nums2=',nums2)print('输出：',s.nextGreatElement(nums1,nums2))

• 测试运行

请输入以空格为分割的字符串数字：2 8 7 3 11 4
请输入以空格为分割的字符串数字：2 10 8 0 7 1 3 11 9 4
输入nums1= [2, 8, 7, 3, 11, 4]        nums2= [2, 10, 8, 0, 7, 1, 3, 11, 9, 4]
x= 2
append later stack= [2]
x= 10
stack[-1]= 2 current stack= [2]
current answer= {2: 10}
append later stack= [10]
x= 8
append later stack= [10, 8]
x= 0
append later stack= [10, 8, 0]
x= 7
stack[-1]= 0 current stack= [10, 8, 0]
current answer= {2: 10, 0: 7}
append later stack= [10, 8, 7]
x= 1
append later stack= [10, 8, 7, 1]
x= 3
stack[-1]= 1 current stack= [10, 8, 7, 1]
current answer= {2: 10, 0: 7, 1: 3}
append later stack= [10, 8, 7, 3]
x= 11
stack[-1]= 3 current stack= [10, 8, 7, 3]
current answer= {2: 10, 0: 7, 1: 3, 3: 11}
stack[-1]= 7 current stack= [10, 8, 7]
current answer= {2: 10, 0: 7, 1: 3, 3: 11, 7: 11}
stack[-1]= 8 current stack= [10, 8]
current answer= {2: 10, 0: 7, 1: 3, 3: 11, 7: 11, 8: 11}
stack[-1]= 10 current stack= [10]
current answer= {2: 10, 0: 7, 1: 3, 3: 11, 7: 11, 8: 11, 10: 11}
append later stack= [11]
x= 9
append later stack= [11, 9]
x= 4
append later stack= [11, 9, 4]
输出： [10, 11, 11, 11, -1, -1]  # 

4. 运行结果

总结

1. 输入的问题：

若主函数改为如下代码：注意nums1,nums2的输入

if __name__ == '__main__':s = Solution()nums1 = input('请输入以空格为分割的字符串数字：').split() ###nums2 = input('请输入以空格为分割的字符串数字：').split() ###print('输入nums1=',nums1,'      ','nums2=',nums2)print('输出：',s.nextGreatElement(nums1,nums2))

注意此时观察列表：

请输入以空格为分割的字符串数字：2 8 7 3 11 4
请输入以空格为分割的字符串数字：2 10 8 0 7 1 3 11 9 4#1.输入为input('请输入以空格为分割的字符串数字：').split()输入nums1= ['2', '8', '7', '3', '11', '4']        nums2= ['2', '10', '8', '0', '7', '1', '9', '4']
#看列表中的数字带有 ‘’ 即字符数字
----------------------------------------
#2.输入为：list(map(int,input('请输入以空格为分割的字符串数字：').split()))输入nums1= [2, 8, 7, 3, 11, 4]        nums2= [2, 10, 8, 0, 7, 1, 3, 11, 9, 4]
# 看列表中的项为纯数字

字符数字串与纯数字输入的差别导致结果的不同

• 输入是纯字符串

请输入以空格为分割的字符串数字：2 8 7 3 11 4
请输入以空格为分割的字符串数字：2 10 8 0 7 1 3 11 9 4
输入nums1= ['2', '8', '7', '3', '11', '4']        nums2= ['2', '10', '8', '0', '7', '1', '9', '4']
x= 2
append later stack= ['2']
x= 10
append later stack= ['2', '10']#①
'''
这里已经有问题了 因为此时stack[-1]=2,且stack[-1]8', '9', '9', '9', '9', -1]
因此，我认为 输入字符数字串 只能判断0-9之内数字大小
'''
x= 8
stack[-1]= 10 current stack= ['2', '10']
current answer= {'10': '8'}
stack[-1]= 2 current stack= ['2']
current answer= {'10': '8', '2': '8'}
append later stack= ['8']
x= 0
append later stack= ['8', '0']
x= 7
stack[-1]= 0 current stack= ['8', '0']
append later stack= ['8', '7']
x= 1
append later stack= ['8', '7', '1']
x= 3
stack[-1]= 1 current stack= ['8', '7', '1']
current answer= {'10': '8', '2': '8', '0': '7', '1': '3'}
append later stack= ['8', '7', '3']
x= 11
append later stack= ['8', '7', '3', '11']
x= 9
stack[-1]= 11 current stack= ['8', '7', '3', '11']
current answer= {'10': '8', '2': '8', '0': '7', '1': '3', '11': '9'}
current answer= {'10': '8', '2': '8', '0': '7', '1': '3', '11': '9', '3': '9'}
stack[-1]= 7 current stack= ['8', '7']
current answer= {'10': '8', '2': '8', '0': '7', '1': '3', '11': '9', '3': '9', '7': '9
stack[-1]= 8 current stack= ['8']
current answer= {'10': '8', '2': '8', '0': '7', '1': '3', '11': '9', '3': '9', '7': '9}
append later stack= ['9']
x= 4
append later stack= ['9', '4']
输出： ['8', '9', '9', '9', '9', -1]

2. 字符数字之间的比较：

⭐⭐在python中是可以进行字符串比较大小的：
都是从左至右，一位一位的进行比较，

• 如果第一位a的字符集编码大于b的字符集编码，那么这个结果就是：a > b；反之则第二位进行比较，以此类推。

>>> '10'<'2' # 因为1<2
True
>>> '10'<'8' # 因为1<8
True
>>> '1'<'3'
True
>>> '1'<'30'
True
>>> '40'<'30' # 4>3
False
>>> '48'<'30'
False
>>> '123'>'124'
False

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！