来自刘翀的问题
【算法:一个有序数组(从小到大排列),数组中的数据有正有负,求这个数组中的最小绝对值一个简单的思路,就是一次性遍历数组,求出数组的元素的绝对值的最小值,这样的时间复杂度为O(n).但】
算法:一个有序数组(从小到大排列),数组中的数据有正有负,求这个数组中的最小绝对值
一个简单的思路,就是一次性遍历数组,求出数组的元素的绝对值的最小值,这样的时间复杂度为O(n).但是,这样就浪费了题目的一个条件:数组是已经排好序的.所以,需要对原来的题目进行转换.考虑到数组有序,则元素绝对值的最小值为数组中最大负数的绝对值与最小非负数的绝对值的最小值.于是,题目事实上是去查找原数组中负数集合中的最大值.(为什么就不是非负数集合中的最小值呢?怎么判断出来一定是负数的?)
1回答
2020-10-03 01:25