作者：dabing🧁

算法小白开始算法学习了，从最简单的开始，一步一步来，这里记录一下。笔记基于自己能看懂～～

第三节～我真的好懒啊啊啊啊😶‍🌫️

这节课基本上都是睡觉前听听有些许迷糊，所有后面补的时候是直接做题的，因为听都听过思路了是可以做题直接做的了。

	题目：
	有序数组中找到num
	有序数组中找到>=num最左的位置
	有序数组中找到<=num最右的位置
	局部最小值问题
	哈希表使用的code讲解
	有序表使用的code讲解

# 1. 二分法查找

	public static void main(String[] args) {
	int times=10000;
	int maxNum=100;
	int maxLen=10;
	boolean succeed = true;
	for (int i = 0; i < times; i++) {
	int num=(int)(Math.random()*(maxNum+1));
	int[] arr=randomArr(maxLen,maxNum);
	if(find(arr,num) != testFind(arr,num)){
	System.out.println("出错了！");
	succeed = false;
	break;
	}
	}
	System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	}

	// 有序数组中找到 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;
	}
	if(arr[mid]<num){
	L=mid+1;
	}
	if(arr[mid]>num){
	R=mid-1;
	}
	}
	return false;

	}


	// 对数器
	public static int[] randomArr(int maxLen,int maxNum){
	int length= (int)(Math.random() * (maxLen+1));
	int[] arr=new int[length];
	for (int i = 0; i < length; i++) {
	arr[i]=(int)(Math.random()* (maxNum+1));
	}
	Arrays.sort(arr);
	return arr;
	}
	// 打印数组
	public static void printArr(int[] arr){
	for (int i = 0; i < arr.length; i++) {
	System.out.print(arr[i]+" ");
	}
	System.out.println();
	}
	// 对数
	public static boolean testFind(int[] arr,int num){
	for (int cur : arr) {
	if(cur==num)
	return true;
	}
	return false;
	}

# 2. 有序数组中找到 >=num 最左的位置

	/**
	* 有序数组中找到 >=num 最左的位置
	* 如有序数组 [1,2,2,2,3,5,8,9,11]
	* num=2;
	* 则 >=2 的最左下标为 1.
	*
	*/
	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 index=-1;
	while (L<=R){
	int mid=(L+R)/2;
	if(arr[mid]>=num){
	index=mid;
	R=mid-1;
	}else {
	L=mid+1;
	}
	}
	return index;
	}

	// 随机有序数组
	public static int[] randomArr(int maxLen,int maxNum){
	int length= (int)(Math.random() * (maxLen+1));
	int[] arr=new int[length];
	for (int i = 0; i < length; i++) {
	arr[i]=(int)(Math.random()* (maxNum+1));
	}
	Arrays.sort(arr);
	return arr;
	}

	// 对数
	public static int testIndex(int[] arr,int num){
	for (int i = 0; i < arr.length; i++) {
	if(arr[i]>=num){
	return i;
	}
	}
	return -1;
	}

	public static void main(String[] args) {
	int times=50000;
	int maxNum=100;
	int maxLen=10;
	boolean succeed = true;
	for (int i = 0; i < times; i++) {
	int num=(int)(Math.random()*(maxNum+1));
	int[] arr=randomArr(maxLen,maxNum);
	if(mostLeftNoLessNumIndex(arr,num) != testIndex(arr,num)){
	System.out.println("出错了！");
	succeed = false;
	break;
	}
	}
	System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

# 3. 局部最小值

	/**
	* 局部最小值问题
	* 序列：无序，但任意相邻的数不相等
	* 局部最小：
	* 1）0 1 x x x x ..... 第一个 0 是局部最小
	* 2) ....x x x x 8 2 最后的 2 是局部最小
	* 3）...x 8 3 9 x x x 中间的 3 是局部最小
	*/
	public class BSAwesome {
	/**
	* 局部最小值下标
	*/
	public static int oneMinIndex(int[] arr){
	if(arr==null \|\| arr.length==0){
	return -1;
	}
	int N=arr.length;
	if(N==1){
	return 0;
	}
	if(arr[0]<arr[1]){
	return 0;
	}
	if(arr[N-1]<arr[N-2]){
	return N-1;
	}

	int L=0;
	int R=N-1;
	while(L< R-1){
	int mid=(L+R)/2;
	if(arr[mid]<arr[mid-1] && arr[mid]<arr[mid+1]){
	return mid;
	}else if(arr[mid]>arr[mid-1]){
	R=mid-1;
	}else {
	L=mid+1;
	}

	}
	return arr[L] < arr[R] ? L : R;
	}

	// 随机无序相邻不等序列
	public static int[] randomArr(int maxLen,int maxNum){
	int length= (int)(Math.random() * (maxLen+1));
	int[] arr=new int[length];
	if(length>0){
	arr[0]=(int)(Math.random()* (maxNum+1));
	for (int i =1 ;i<length;i++ ) {
	do{
	arr[i]=(int)(Math.random()* (maxNum+1));
	}while(arr[i]==arr[i-1]);

	}
	}
	return arr;
	}
	// 打印数组
	public static void printArr(int[] arr){
	for (int i = 0; i < arr.length; i++) {
	System.out.print(arr[i]+" ");
	}
	System.out.println();
	}

	// 对数
	public static boolean test(int[] arr,int minIndex){
	if (arr.length == 0) {
	return minIndex == -1;
	}
	int left = minIndex - 1;
	int right = minIndex + 1;
	boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
	boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
	return leftBigger && rightBigger;
	}

	public static void main(String[] args) {
	int maxLen = 100;
	int maxValue = 200;
	int testTime = 1000000;
	System.out.println("测试开始");
	for (int i = 0; i < testTime; i++) {
	int[] arr = randomArr(maxLen, maxValue);
	int ans = oneMinIndex(arr);
	if (!test(arr, ans)) {
	printArr(arr);
	System.out.println(ans);
	break;
	}
	}
	System.out.println("测试结束");
	}
	}

# 4. 时间复杂度

列一些常见的时间复杂度，由好到差：

O(1)、O(logN)、O(N)、O(N*logN)

O(N^2)、O(N3)、O(N^k)

O(2^n)、O(3n)、O(k^n)

O(n!)

# 5. 哈希表 HashMap、有序表 TreeMap

HashMap 哈希表，增删改查都是常数时间。put、containsKey、remove

基础类型按内容查，非基础类型按引用地址查。所以空间耗损也是如果你是地址，那只是占用地址 8 字节而已，两个都是地址那就是 16 字节。

TreeMap 有序表的一些特别方法：它的时间复杂度是 O (logN)

非基础类型不能直接用有序表，因为 key 一定要是能比较的，你可以在你的类里面添加上比较器

	TreeMap<Integer, String> treeMap1 = new TreeMap<>();

	treeMap1.put(3, "我是3");
	treeMap1.put(0, "我是0");
	treeMap1.put(7, "我是7");
	treeMap1.put(2, "我是2");
	treeMap1.put(5, "我是5");
	treeMap1.put(9, "我是9");

	System.out.println(treeMap1.containsKey(7));
	System.out.println(treeMap1.containsKey(6));
	System.out.println(treeMap1.get(3));

	treeMap1.put(3, "他是3");
	System.out.println(treeMap1.get(3));

	treeMap1.remove(3);
	System.out.println(treeMap1.get(3));

	System.out.println(treeMap1.firstKey()); //0
	System.out.println(treeMap1.lastKey()); //9
	// <=5 离 5 最近的 key 告诉我
	System.out.println(treeMap1.floorKey(5)); //5
	// <=6 离 6 最近的 key 告诉我
	System.out.println(treeMap1.floorKey(6)); //5
	// >=5 离 5 最近的 key 告诉我
	System.out.println(treeMap1.ceilingKey(5)); //5
	// >=6 离 6 最近的 key 告诉我
	System.out.println(treeMap1.ceilingKey(6)); //7

	// 非基础类型不能直接用有序表，因为 key 一定要是能比较的，你可以在你的类里面添加上比较器
	// Node node3 = new Node(3);
	// Node node4 = new Node(4);
	// TreeMap<Node, String> treeMap2 = new TreeMap<>();
	// treeMap2.put (node3, "我是 node3");
	// treeMap2.put (node4, "我是 node4");

算法

# 1. 二分法查找

# 2. 有序数组中找到 >=num 最左的位置

# 3. 局部最小值

# 4. 时间复杂度

# 5. 哈希表 HashMap、有序表 TreeMap

成功日记