输入一个整形升序整数数组array和正数n,求该数组所有正数之和。要求:编写以下函数: int positive_sum(

有一个已经排序的数组(升序)数组中可能有正数、负数或0,求数组中元素的绝对值最小的数要求,不能用顺序比较的方法(复杂度需要小于O(n))可以使用任何語言实现

    1.数组中的元素全为正,取最左边的数字;

    2.数组中的元素全为负取最右边的数字的绝对值;

    3.数组中有正数有负数,就用二分法查找判断中间元素的符号

下面是根据上面的想法的代码实现,应该还会有漏洞

//求取数组中绝对值最小的数字 //返回两个数中较小的数 //数组中嘚数全是负数取最右边的数 //数组中的数全是正数,取最左边的数 //数组有正有负二分查找

有一个已经排序的数组(升序)数组中可能有正数、负数或0,求数组中元素的绝对值最小的数要求,不能用顺序比较的方法(复杂度需要小于O(n))可以使用任何語言实现

给定数组是已经排好序的,且是升序没有重复元素。

一个简单的思路就是一次性遍历数组,求出数组的元素的绝对值的最小徝这样的时间复杂度为O(n)。

但是这样就浪费了题目的一个条件:数组是已经排好序的。所以需要对原来的题目进行转换。考虑到数组囿序利用二分查找原理。

求数组中绝对值最小的元素与0离得最近绝对值越小。基于这个原理设计代码

(3)有正有负,利用二分查找找到0的插入位置如果正好找到0的位置,0就是绝对值最小的元素

如果没有找到0,插入位置的左右元素比较绝对值大小 返回较小者OK。

* 题目: 排序数组中绝对值最小元素 // 找到0的插入位置 // 中间元素等于目标

参考资料

 

随机推荐