认识时间复杂度和简单排序算法

认识时间复杂度和简单排序算法 异或运算

实现swap：

int a=1;
int b=2;
a=a^b;
b=a^b;
a=a^b;

可以是相同数值但不能是存放在同一个地址，注意数组的i,j互换；
例题1：
有n个数，除了一个奇数个的数，其他都为偶数个，求出个数为奇数的数值。
题解：直接对所有元素进行异或运算（^）最终结果便是。
例题2：
有n个数，有两种数出现奇数次，其他都为偶数个，求出个数为奇数的数值。
题解：对所有元素进行异或运算（^），最终一定会有a异或b!=0，假设a与b在第八位是不相同，那么a与b一定会被分成两类，一类含有a一类含有b，那么对其中一类第八位全是1的进行异或，最终得到a或b，将得到的结果对（）a异或b）再进行异或，运算结果即为另一个。

提取最右侧的1(第二题题解）

int eor = 0;
for(int i = 0 ; i < arr.length ; i++ )
	eor ^= arr[i];

int rightOne = eor & (~eor + 1);

int onlyOne = 0;
for(int cur : arr ){
	if((cur & rightOne) == 1){
		onlyOne ^= cur;
	}
}
System.out.println(onlyOne + " " + (ero ^ onlyOne);

插入排序

时间复杂度O(n^2)，空间复杂度O(1)

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

二分

1. 在一个有序数组中找某个数是否存在；
2. 在一个有序数组中找>=某个数最左测得位置；
3. 局部最小值问题；

对数器

不依赖oj进行测试，本质就是对两个独立思路的进行测试，用equal来判断两个数据是否正确就行
随机生成一个数组用于测试

	public static int[] generateRandomArray(int maxSize, int maxValue) {
		
		//Math.random()    [0,1)所有的小数，等概率返回一个
		//Math.random()*N     [0,N)所有的小数，等概率返回一个
		//(int)Math.random()*N    [0,N-1]所有的小数，等概率返回一个
		int[] arr = new int[(int)((maxSize+1) * Math.random())];
		for(int i = 0 ; i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5692436.html