一组有序数(从小到大排列),有负有正,找出绝对值最小值。(C或C++)
package main import . "fmt" // 一组有序数(从小到大排列),有负有正,找出绝对值最小值。(Go) func findAbsMin(s []int) int { var i int = 0 for s[i] < 0 { i++ } if s[i]+s[i-1] <= 0 { return s[i] } else { return s[i-1] } } func main() { ss := []int{-4, -3, -2, -1, 1, 2, 3, 4, 5, 6} res := findAbsMin(ss) Printf("在切片%v中,绝对值最小的是: %v\n", ss, res) }
简单明了
public int minAbs(int[] a) { int lo = 0, hi = a.length-1; while(lo < hi) { int mid = (lo+hi)>>1; if(a[mid] < 0) { if(a[mid+1] < 0) lo = mid+1; else return Math.min(-a[mid], a[mid+1]); } else { if(mid == 0) return a[mid]; if(a[mid-1] >= 0) hi = mid-1; else return Math.min(a[mid], -a[mid-1]); } } return a[lo]; // 全负或全正 }
}
int getMin(vector<int> a, int n) { assert(n > 0); if (a[0] >= 0) return a[0]; if (a[n-1] <= 0) return (-1) * a[n-1]; int l = 0; int r = n-1; int res = min((-1)*a[0], a[n-1]); while (l < r) { int m = (l + r) >> 1; if (a[m] > 0) { res = min(res, a[m]); r = m-1; } else if (a[m] < 0) { res = min(res, (-1)*a[m]); l = m+1; } else return a[m]; } return abs(a[l]); } o(logN)时间复杂度
#include <stdio.h> #include <vector> using namespace std; static int GetMin(const vector<int> &data, int begin, int end){ //循环到只剩下两个相邻数字,或者整个序列都是相同符号 if(end - begin == 1 || data[begin] * data[end] >= 0){ return abs(data[end]) > abs(data[begin]) ? data[begin] : data[end]; } int k = (begin + end) / 2; //对异号的序列查找 if(data[begin] * data[k] > 0){ return GetMin(data, k, end); } return GetMin(data, begin, k); } int FindAbsMin(const vector<int> &data){ int m = GetMin(data, 0, data.size() - 1); printf("%d", m); return m; } int main(){ vector<int> data; int Num[] = {-4,-3,-2,-1}; for(int i = 0; i < sizeof(Num) / sizeof(Num[0]); ++i){ data.push_back(Num[i]); } FindAbsMin(data); return 0; }
int findMinNum(int nums[], int ilen) { int iFirst = 0; int iSecond = 0; int iIndex = 0; for (; iIndex < ilen; iIndex++) { iFirst = nums[iIndex]; iSecond = nums[iIndex + 1]; if (iFirst < 0 && iSecond >= 0) { break; } } return (-iFirst > iSecond) ? iSecond : -iFirst; } int main () { int sss[] = { -4 - 3, -2, -1, 1, 2, 3, 6, 9 }; int ss = findMinNum(sss,sizeof(sss)/sizeof(int)); return 0; }