关注
在数组中找到一个局部最小的位置
【题目】
定义局部最小的概念。arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0]<arr[1],那么arr[0]是局部最小;如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i]<arr[i-1]又有arr[i]<arr[i+1],那么arr[i]是局部最小。
给定无序数组arr,已知arr中任意两个相邻的数都不相等,写一个函数,只需返回arr中任意一个局部最小出现的位置即可。
public int getLessIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return -1; // no exist
}
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
05-18 13:26
西安电子科技大学 电子信息类 点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
861005次浏览 13709人参与
# 机械制造薪资爆料 #
324524次浏览 3771人参与
# 晒一晒我的offer #
3509740次浏览 55644人参与
# 24届软开秋招面试经验大赏 #
1062927次浏览 16916人参与
# 如果重来一次你还会读研吗 #
74582次浏览 725人参与
# 国企vs私企,你更想去? #
24538次浏览 277人参与
# 金三银四,你有感觉到吗 #
334179次浏览 4261人参与
# 0offer是寒冬太冷还是我太菜 #
433185次浏览 4977人参与
# offer决赛圈,我是怎么选的 #
203674次浏览 2289人参与
# 我在牛爱网找对象 #
51586次浏览 341人参与
# 你会选择考研还是直接就业 #
79537次浏览 923人参与
# 求职遇到的搞笑事件 #
19901次浏览 290人参与
# 我发现了面试通关密码 #
356048次浏览 6713人参与
# 好工作要具备的条件有哪些? #
3977次浏览 58人参与
# 实习与准备秋招该如何平衡 #
182255次浏览 3253人参与
# OPPO求职进展汇总 #
99868次浏览 1076人参与
# 职业发展规划如何回答 #
12640次浏览 88人参与
# 重来一次,我还会选择这个专业吗 #
100989次浏览 1581人参与
# 海康威视求职进展汇总 #
103808次浏览 1233人参与
# 机械专业只有考研才有出路吗 #
23285次浏览 414人参与