4)局部最小值问题
一个无序数组，任意两个相邻元素都不相等，找到一个局部最小值。
package complexity01; /** * @author Corley * @date 2021/10/4 9:45 * @description LeetCodeAlgorithmZuo-complexity01 */ public class BinarySearchLocalMin { public static int getLessIndex(int[] arr) { if (null == arr || 0 == arr.length) { return -1; } if (1 == arr.length || arr[0] < arr[1]) { return 0; } if (arr[arr.length - 1] < arr[arr.length - 2]) { return arr.length - 1; } int left = 1, right = arr.length - 2; int mid; while (left < right) { mid = left + ((right - left) >> 1); if (arr[mid - 1] < arr[mid]) { right = mid - 1; } else if (arr[mid + 1] < arr[mid]) { left = mid + 1; } else { return mid; } } return left; } public static void main(String[] args) { System.out.println(getLessIndex(new int[]{0, 2, 5, 5, 6, 7, 7, 7, 9, 12})); System.out.println(getLessIndex(new int[]{8, 2, 5, 7, 6, 4, 7, 2, 3, 4})); System.out.println(getLessIndex(new int[]{7, 2, 8, 5, 6, 9, 7, 3, 9, 0})); } }
5.异或运算
认识异或运算
异或运算:相同为0，不同为1
同或运算:相同以1，不同为0
能长时间记住的概率接近0%
所以，异或运算就记成无进位相加!
异或运算的性质
1)0^N==N
N^N == 0
2)异或运算满足交换律和结合率
上面的两个性质用无进位相加来理解就非常的容易
如何不用额外变量交换两个数
可以进行这种操作的前提是变量属于不同的对象，即指向不同的内存，否则对象的数值会被置为0，但是允许两个对象的值相等。
一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这一个数。
代码：
public static void getOneOddTimes(int[] arr) { int eor = 0; for (int i = 0; i < arr.length; i++) { eor ^= arr[i]; } System.out.println(eor); }
怎么把一个int类型的数，提取出最右侧的1
方法：N & ((~N) + 1)
一个数组中有两个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两个数。
如下：
/* 一个数组中有两个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两个数。 */ public static void getTwoOddTimes(int[] arr) { int eor1 = 0; for (int j : arr) { eor1 ^= j; } // 提取最右边的1 int rightOne = eor1 & (~eor1 + 1); int eor2 = 0; for (int j : arr) { if ((j & rightOne) != 0) { eor2 ^= j; } } int num1 = eor2, num2 = eor1 ^ eor2; System.out.println(num1 + " " + num2); } public static void main(String[] args) { int[] arr = {1, 2, 2, 4, 6, 6, 6, 6, 6, 4, 4, 4, 7, 7, 6, 7, 8, 8}; getTwoOddTimes(arr); }
给定一个数，计算这个数的二进制形式中1的个数。
public static int bit1Count(int num) { int count = 0; int rightOne; while (num != 0) { rightOne = num & (~num + 1); count++; num ^= rightOne; } return count; } public static void main(String[] args) { // int[] arr = {1, 2, 2, 4, 6, 6, 6, 6, 6, 4, 4, 4, 7, 7, 6, 7, 8, 8}; // getTwoOddTimes(arr); System.out.println(Integer.toBinaryString(12345)); System.out.println(bit1Count(12345)); }
总结
左神极力推荐的对数器是检验算法实现正确性的有力工具，可以覆盖几乎所有情况的测试用例，无死角实现对算法的验证。同时异或也是可以在算法实现中加快运算效率的技巧。
