vps服务器中的网站不显示图片,网站开发的网站,明天上海全面封控5天,网站建设百度搜索到左边的图文章目录选择排序冒泡排序插入排序二分二分查找某个数是否存在在arr上#xff0c;找满足大于等于value的最左位置在arr上#xff0c;找满足小于等于value的最右位置局部最小值异或选择排序
O(n^2)
public class Code01_SelectionSort {public static void selectionSort(in…
文章目录选择排序冒泡排序插入排序二分二分查找某个数是否存在在arr上找满足大于等于value的最左位置在arr上找满足小于等于value的最右位置局部最小值异或选择排序
O(n^2)
public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr null || arr.length 2) {return;}// 0 ~ N-1 找到最小值在哪放到0位置上// 1 ~ n-1 找到最小值在哪放到1 位置上// 2 ~ n-1 找到最小值在哪放到2 位置上for (int i 0; i arr.length - 1; i) {int minIndex i;for (int j i 1; j arr.length; j) { // i ~ N-1 上找最小值的下标 minIndex arr[j] arr[minIndex] ? j : minIndex;}swap(arr, i, minIndex);}}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}
}冒泡排序
O(n^2)
public class Code02_BubbleSort {public static void bubbleSort(int[] arr) {if (arr null || arr.length 2) {return;}// 0 ~ N-1// 0 ~ N-2// 0 ~ N-3for (int e arr.length - 1; e 0; e--) { // 0 ~ eboolean flag true;for (int i 0; i e; i) {if (arr[i] arr[i 1]) {swap(arr, i, i 1);flag false;}}if (false) {break;}}}// 交换arr的i和j位置上的值public static void swap(int[] arr, int i, int j) {arr[i] arr[i] ^ arr[j];arr[j] arr[i] ^ arr[j];arr[i] arr[i] ^ arr[j];}
}插入排序
O(n^2)
public class Code03_InsertionSort {public static void insertionSort(int[] arr) {if (arr null || arr.length 2) {return;}// 不只1个数for (int i 1; i arr.length; i) { // 0 ~ i 做到有序for (int j i - 1; j 0 arr[j] arr[j 1]; j--) {swap(arr, j, j 1);}}}// i和j是一个位置的话会出错public static void swap(int[] arr, int i, int j) {arr[i] arr[i] ^ arr[j];arr[j] arr[i] ^ arr[j];arr[i] arr[i] ^ arr[j];}
} 二分
O(log2^N)
二分查找某个数是否存在
public class Code04_BSExist {public static boolean exist(int[] sortedArr, int num) {if (sortedArr null || sortedArr.length 0) {return false;}int L 0;int R sortedArr.length - 1;int mid 0;// L..Rwhile (L R) { // L..R 至少两个数的时候mid L ((R - L) 1);if (sortedArr[mid] num) {return true;} else if (sortedArr[mid] num) {R mid - 1;} else {L mid 1;}}return sortedArr[L] num;}
}在arr上找满足大于等于value的最左位置
public class Code05_BSNearLeft {public static int nearestIndex(int[] arr, int value) {int L 0;int R arr.length - 1;int index -1; // 记录最左的对号while (L R) { // 至少一个数的时候int mid L ((R - L) 1);if (arr[mid] value) {index mid;R mid - 1;} else {L mid 1;}}return index;}
}在arr上找满足小于等于value的最右位置
public class Code05_BSNearRight {public static int nearestIndex(int[] arr, int value) {int L 0;int R arr.length - 1;int index -1; // 记录最右的对号while (L R) {int mid L ((R - L) 1);if (arr[mid] value) {index mid;L mid 1;} else {R mid - 1;}}return index;}
}局部最小值
arr 无序任意俩个相邻位置不等返回一个局部最小的位置
public class Code06_BSAwesome {public static int getLessIndex(int[] arr) {if (arr null || arr.length 0) {return -1;}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;}
}异或
异或无进位相加 相同为0不同为1 同或无进位相加 相同为1不同为0
arr中只有一种数出现奇数次找出并打印 arr中有两种数出现奇数次找出并打印
public class Code07_EvenTimesOddTimes {// arr中只有一种数出现奇数次public static void printOddTimesNum1(int[] arr) {int eor 0;for (int i 0; i arr.length; i) {eor ^ arr[i];}System.out.println(eor);}// arr中有两种数出现奇数次public static void printOddTimesNum2(int[] arr) {int eor 0;for (int i 0; i arr.length; i) {eor ^ arr[i];}// a 和 b是两种数// eor ! 0// eor最右侧的1提取出来// eor : 00110010110111000// rightOne :00000000000001000int rightOne eor (-eor); // 提取出最右的1int onlyOne 0; // eorfor (int i 0 ; i arr.length;i) {// arr[1] 111100011110000// rightOne 000000000010000if ((arr[i] rightOne) ! 0) {onlyOne ^ arr[i];}}System.out.println(onlyOne (eor ^ onlyOne));}
}
