左神算法新手班课程学习笔记03
纳西妲首席爹粉
2023-01-02 23:22
阅读1606
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
03 介绍二分法，介绍时间复杂度、动态数组、哈希表和有序表
内容：
二分法
使用二分法解决不同的题目
找到中点，然后砍成两半。如果有序，根据中点的值大小，判断继续找上一半还是下一半，循环往复，直到找不到。
时间复杂度
动态数组
按值传递、按引用传递
哈希表
有序表
题目：
有序数组中找到num
public static boolean find(int[] arr, int num){
//边界条件
if(arr == null || arr.length == 0){
return false;
}
int L = 0;
int R = arr.length - 1;
//二分开始
while(L <= R){
int mid = (L + R) / 2;
if(arr[mid] == num){
return true;
}else if( arr[mid] < num){
//中点的值小于num，在数组后半部分找
//把数组的左起点的位置改到中点后面的位置
L = mid +1;
}else if{
//中点的值大于num，在数组前半部分找
//把数组的右终点的位置改到中点前面的位置
R = mid -1;
}
}
return false;
}
有序数组中找到>=num最左的位置
public static int MostLeftNoLessNumIndex(int[] arr, int num){
//边界条件
if(arr == null || arr.length == 0){
return -1;
}
int L = 0;
int R = arr.length - 1;
int ans = -1;
while(L <= R){
int mid = (L + R)/2;
if(arr[mid] >= num){
ans = mid;
R = mid - 1;
}else{
//arr[mid] < num
L = mid +1;
}
}
return ans;
}
有序数组中找到<=num最右的位置
public static int MostLeftNoLessNumIndex(int[] arr, int num){
//边界条件
if(arr == null || arr.length == 0){
return -1;
}
int L = 0;
int R = arr.length - 1;
int ans = -1;
while(L <= R){
int mid = (L + R)/2;
if(arr[mid] <= num){
ans = mid;
L = mid + 1;
}else{
//arr[mid] > num
R = mid -1;
}
}
return ans;
}
局部最小值问题
给定一个无序 数组，该数组的任意两个相邻的位置的和不等
局部最小的定义，0位置的值要小于1位置的值，N-1位置的值要小于N-2位置的值，而i位置的值要比相邻左右位置要小。
要求返回一个局部最小即可。
public static 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;
}
哈希表使用的code讲解
有序表使用的code讲解
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
