Java基础之时间复杂度

一、基础 - 简单排序算法

选择排序

public static void selectionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		int minIndex = i;	//记录最小值位置
		for (int j = i + 1; j < arr.length; j++) {
			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;
}

冒泡排序

public static void bubbleSort(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }
  for (int e = arr.length - 1; e > 0; e--) {
    for (int i = 0; i < e; i++) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);	//把较大数交换到后面
      }
    }
  }
}

public static void swap(int[] arr, int i, int j) {
    //只有i，j两个位置不同时可以这么写
    //否则会将数据抹成0
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

插入排序

public static void insertionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 1; i < arr.length; i++) {
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
			swap(arr, j, j + 1);
		}
	}
}

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];
}

二分法的详解与扩展

1）在一个有序数组中，找某个数是否存在

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;
	while (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;
}

2）在一个有序数组中，找 >= 某个数最左侧的位置

// 在arr上，找满足>=value的最左位置
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;
}

3）局部最小值问题

//找到一个局部最小值就返回，	会优先找到左边的	
	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;
			}
		}
        //left == right 此时的	left 就是下一次的mid
		return left;
	}

二、拓展 - 异或运算

异或运算的性质与扩展

0^N == N N^N == 0
异或运算满足交换律和结合率
不用额外变量交换两个数
一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数

//找一个出现了奇数次的数
	public static void printOddTimesNum1(int[] arr) {
		int eO = 0;
		for (int cur : arr) {
			eO ^= cur;
		}
		System.out.println(eO);
	}
	//找两个出现了奇数次的数
	public static void printOddTimesNum2(int[] arr) {
		int eO = 0, eOhasOne = 0;
		for (int curNum : arr) {
			eO ^= curNum;
		}
		int rightOne = eO & (~eO + 1);	//提取最右边的1出来
		for (int cur : arr) {
            //当这个数的最右边一位1 与rightOne 相同时，才将它异或进去
			if ((cur & rightOne) != 0) {
				eOhasOne ^= cur;
			}
		}
		System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
	}