无序数组中找到左侧比他小右侧比他大的数_无序数组中寻找一个数,左值比它小,右值比它大

作者：AllinToyou | 2024-03-13 04:04:49

踩

无序数组中寻找一个数,左值比它小,右值比它大

无序数组中找到左侧比他小右侧比他大的数，要求时间复杂度在O(n)。思路是单独创建一个标记数组，先从左往右遍历(i=0开始)，找最大，如果是当前的最大，max标记位置和当前游标有max=i，则设置标记数组位置+1；同理，从len-1的位置，找最小，即从右往左遍历（i=len-1开始），找最小，如果是当前的最小，min标记位置和当前游标min=i，并把标记数组位置+1；最终标记数组中如果既是比左侧大的数又是比右侧小的数的值为2，用标记数组过滤一次原数组就可以得到。时间复杂度为3n，空间为n

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/227679