【算法】局部最小值问题
2022/1/3 22:37:22
本文主要是介绍【算法】局部最小值问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
局部最小值是指在一个数组中,假如一个元素比它的左右相邻元素(如果存在)都小,那么这个元素就是局部最小值。
题目描述
给定一个不包含相同元素的整数数组,求一个局部最小值。
题解
1)数组第一个元素比第二个元素小,即为局部最小值。
2)数组最后一个元素比它前一个元素小,即为局部最小值。
3)若不满足,那么局部最小值必可在数组首尾两元素之间的某个位置取得。此时可以采用二分法思想,看中间位置是否符合条件,不符合就分成两部分,从不符合的那一边继续操作。
public class LocalMinimum { public static int findLM(int[] arr) { if (arr == null || arr.length == 0) { //数组为空或数据长度为0 return -1; } if (arr.length == 1) { //数组只有一个元素即为局部最小值 return 0; } if (arr[0] < arr[1]) { //数组第一个元素比第二个元素小,即为局部最小值 return 0; } if (arr[arr.length - 1] < arr[arr.length - 2]) {//数组最后一个元素比它前一个元素小,即为局部最小值 return arr.length - 1; } //上述条件均不满足,局部最小值必在数组内部取得 //用二分法思想求解 int left = 0, right = arr.length - 1; int mid; 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 -1; } public static void main(String[] args) { //测试 int[] arr = {4,3,6,8,2,1,5,7}; System.out.println(findLM(arr)); } }
时间复杂度为O(logN)
这篇关于【算法】局部最小值问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?