二分法
分别对应一个简单二分以及对数器写法
// arr保证有序
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) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return false;
}
// for test
public static boolean test(int[] sortedArr, int num) {
for (int cur : sortedArr) {
if (cur == num) {
return true;
}
}
return false;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 10;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
Arrays.sort(arr);
int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
if (test(arr, value) != find(arr, value)) {
System.out.println("出错了！");
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
在有序数组中找到>=num的最左位置
// arr有序的，>=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) {
//如果当前位置比num大则往左边取，如果当前位置比num小则往右边走
ans = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return ans;
}
// for test（这里以一个O(n)的遍历方式来获取第一个大于等于num的value）
public static int test(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= value) {
return i;
}
}
return -1;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 10;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
Arrays.sort(arr);
int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
if (test(arr, value) != mostLeftNoLessNumIndex(arr, value)) {
printArray(arr);
System.out.println(value);
System.out.println(test(arr, value));
System.out.println(mostLeftNoLessNumIndex(arr, value));
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
局部最小值问题
当前数组无序且任意两个相邻的数不相等
有三种情况
0位置上面的数比1位置上面的数小，因为0左边没数
N-2位置>N-1位置，因为N-1位置右边没数
左边>i<右边 i位置既比左边小也比右边小
返回其中一个局部最小
如果一二情况不成立的话，那么在0-1位置上是一个下降线，在N-2到N-1上面则为一个上升线，那么必然在2到N-3位置上有个局部最小值，那么就可以根据这个规律去进行二分。【如果0到mid的范围是先下降后上扬，那么局部最小就在0到mid的范围内，从而再缩小搜索范围】
代码如下：
// arr 相邻的数不相等！
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;
// L...R 肯定有局部最小
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[] randomArray(int maxLen, int maxValue) {
int len = (int) (Math.random() * maxLen);
int[] arr = new int[len];
if (len > 0) {
arr[0] = (int) (Math.random() * maxValue);
for (int i = 1; i < len; i++) {
do {
arr[i] = (int) (Math.random() * maxValue);
} while (arr[i] == arr[i - 1]);
}
}
return arr;
}
// 也用于测试
public static boolean check(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 printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
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 = randomArray(maxLen, maxValue);
printArray(arr);
int ans = test(arr);
if (!check(arr, ans)) {
printArray(arr);
System.out.println(ans);
break;
}
}
System.out.println("测试结束");
}
时间复杂度
不关心系数，不关心低阶项，只关心最高阶
如冒泡排序：
0，1，2，3，4，5，6，7，8；
我首先要找在八位置上的最大，我要执行8次比较交换，
再找七位置上的最大，我要执行7次比较交换，
再找六位置上的最大，我要执行6次比较交换，
这样就是一个1到8的等差数列
根据等差数列求和的公式
S = na1 + n(n-1)/2d，
由上面的公差为1，可化简为
nn/2 -(1/2-a1)n，所以得到冒泡排序的时间复杂度为O(nn)
时间复杂度由小到大排序为
logN <N<NlogN<NN<N^3 < NK<2N<k^N<n!
有序表用法
里面的操作不像HashMap一样是常数级别的，Tree Map的操作皆为logN级别的
TreeMap不同于HashMap的使用
TreeMap<Integer, String> treeMap1 = new TreeMap<>();
treeMap1.put(3, "我是3");
treeMap1.put(0, "我是3");
treeMap1.put(7, "我是3");
treeMap1.put(2, "我是3");
treeMap1.put(5, "我是3");
treeMap1.put(9, "我是3");
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());
System.out.println(treeMap1.lastKey());
// <=5 离5最近的key告诉我
System.out.println(treeMap1.floorKey(5));
// <=6 离6最近的key告诉我
System.out.println(treeMap1.floorKey(6));
// >=5 离5最近的key告诉我
System.out.println(treeMap1.ceilingKey(5));
// >=6 离6最近的key告诉我
System.out.println(treeMap1.ceilingKey(6));
对于TreeMap如果key是自己定义的引用类型则需要在TreeMap的构造方法里面去写出一个比较器。
