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

认识时间复杂度和简单排序算法,第1张

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

实现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					
										


					

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5692436.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存