数据结构基础一(认识复杂度、对数器、二分法与异或运算)

Scroll Down

评估算法优劣的核心指标

1、时间复杂度(流程决定)
2、额外空间复杂度(流程决定)
3、常数项时间(实现细节决定)

什么是时间复杂度?时间复杂度怎么估算?

1、常数时间的操作

如果一个操作的执行时间不以具体样本量为转移,每次执行时间都是固定时间。称这样的操作为常数时间的操作(执行时间固定的操作)

常见的常数时间的操作
a、常见的算术运算(+、-、*、/、%等)
b、常见的位运算(>>、>>>、 <<、 | 、&、 ^等)
c、赋值、比较、自增、自减操作等
d、数组寻址操作

2、确定算法流程的总操作数量与样本数量之间的表达式关系

a、想象该算法流程所处理的数据状况,要按照最差情况来
b、把整个流程彻底拆分为一个个基本操作,保证每个动作都是常数时间的操作
c、如果数据量为N,看看基本动作的数量和N的关系

3、只看表达式最高阶项的部分

4、如何确定算法流程的时间复杂度
当完成课表达式的建立,只要把最高阶项留下来即可。低阶项都去掉,高阶项的系数也去掉
记为:O(忽略掉系数的高阶项)

5、注意
a、算法的过程,和具体的语言是无关的
b、想分析一个算法流程的时间复杂度的前提,是对该流程非常属于西
c、一定要确保在拆分算法流程时,拆分出来的所有行为都是常数时间的操作。

选择排序( O(n^2) )

个人理解原理:根据当前值,在数组中找最小值的下标 进行交换

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {3,2,9,7,1,6,8,5};
        selectionSort(arr);

        System.out.print("arr====  ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    private static void selectionSort(int[] arr) {
        //如果为空  或者只有一个数 直接返回
        if(arr == null || arr.length < 2){
            return;
        }

        for (int i = 0; i < arr.length-1; i++) {
            //定义一个最小的坐标 最小值在哪个位置上  i~n-1
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                // i ~ N-1 上找最小值的下标
                minIndex = arr[j] < arr[minIndex] ? j:minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    private static void swap(int[] arr, int i, int minIndex) {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

冒泡排序

个人理解:相邻的两个数进行比较,根据需求交换位置


/**
 * @program: Data-Structure
 * @ClassName BubbleSortFirst
 * @description:    冒泡排序  最好时间:O(n)  最坏时间:O(n^2)  平均时间:O(n^2)  额外空间:1  稳定性:稳定
 * @author: hujie
 * @create: 2020-05-20 17:34
 **/
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,2,9,7,1,6,8,5};
//        sort1(arr);
//        int[] arr1 = {5,4,3,1,2};
//        sort2(arr1);
        sort3(arr);
    }

    /**
     * 冒泡排序(未优化) 时间:O(n^2)
     * @param arr
     */
    public static void sort1(int[] arr){
        // 定义一个临时值
        int temp = 0;
        // 要遍历的次数
        for (int i = 0; i < arr.length-1; i++) {
            System.out.format("第 %d 遍:\n", i+1);
            //依次的比较相邻两个数的大小,遍历一次后,把数组中第i小的数放在第i个位置上
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] < arr[j+1]){
                    temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
                System.out.format("第 %d 遍的第%d 次交换:", i+1,j+1);
                for(int count:arr) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            System.out.format("第 %d 遍最终结果:", i+1);
            for(int count:arr) {
                System.out.print(count);
            }
            System.out.println("\n#########################");
        }
    }

    /**
     * 优化一
     * @param arr
     */
    public static void sort2(int[] arr){
        // 定义一个临时值
        int temp = 0;
        // 要遍历的次数
        for (int i = 0; i < arr.length-1; i++) {
            int flag = 1;
            System.out.format("第 %d 遍:\n", i+1);
            //依次的比较相邻两个数的大小,遍历一次后,把数组中第i小的数放在第i个位置上
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] < arr[j+1]){
                    temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag = 0;
                }
                System.out.format("第 %d 遍的第%d 次交换:", i+1,j+1);
                for(int count:arr) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            System.out.format("第 %d 遍最终结果:", i+1);
            for(int count:arr) {
                System.out.print(count);
            }
            System.out.println("\n#########################");

            if(flag == 1){
                return;
            }

        }
    }


    /**
     * 优化二
     * @param arr
     */
    public static void sort3(int[] arr){
        // 定义一个临时值
        int temp = 0;
        int len = arr.length-1;
        // 记录最后一次交换的位置
        int tempPostion = 0;
        // 要遍历的次数
        for (int i = 0; i < arr.length-1; i++) {
            int flag = 1;
            System.out.format("第 %d 遍:\n", i+1);
            //依次的比较相邻两个数的大小,遍历一次后,把数组中第i小的数放在第i个位置上
            for (int j = 0; j < len-i; j++) {
                if(arr[j] < arr[j+1]){
                    temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag = 0;
                    //记录交换的位置
                    tempPostion = j;
                }
                System.out.format("第 %d 遍的第%d 次交换:", i+1,j+1);
                for(int count:arr) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            //把最后一次交换的位置给len,来缩减内循环的次数
            len = tempPostion;
            System.out.format("第 %d 遍最终结果:", i+1);
            for(int count:arr) {
                System.out.print(count);
            }
            System.out.println("\n#########################");

            if(flag == 1){
                return;
            }

        }
    }
}

插入排序

个人理解:从第一个数开始排序,在对下一个数的排序时,保证这个数之前的数组是有序的,在通过比较数值的大小比较,找到该数在小型有序数组的位置

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {3,2,9,7,1,6,8,5};
        insertSort(arr);

        System.out.print("arr====  ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    private static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = i-1; j >=0 && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j+1);
            }
        }

    }

    private static void swap(int[] arr, int i, int j) {
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

额外空间复杂度

要实现一个算法流程,在实现算法流程的过程中,需要开辟一些空间来支持你的算法
作为输入参数的空间,不算额外空间
作为输出结果的空间,不算额外空间

因为这些都是必要的、和实现目标有关的。所以不算额外空间,除此之外,流程如果还需要开辟空间才能让流程继续下去,这部分空间就是额外空间。
如果流程只需要开辟有限几个变量,额外空间复杂度就是O(1).

算法流程的常数项

时间复杂度这个指标,是忽略低阶项和所有常数系数的,难道同样时间复杂度的流程,在实际运行时候就一样的好嘛?当然不是。时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法,还要去在时间上拼优劣,就进入了拼常数时间的阶段,简称瓶常数项

面试、比赛、刷题中,一个问题的最优解是什么意思?

一般情况下,认为解决一个问题的算法流程,在时间复杂度的指标上,一定要尽可能的低,先满足了时间复杂度最低这个指标之后,使用最少的空间的算法流程,叫这个问题的最优解

一般说起最优解都是忽略常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑,二和怎么解决整个问题的思想无关。

常见的时间复杂度

排名从好到差:

O(1)
O(logN)
O(N)
O(N*logN)
O(N^2) O(N^3)...O(N^k)
O(2^N) O(3^N) ... O(k^N)
O(N!)

对数器

1、想要测的方法a
2、实现复杂度不好但是容易实现的方法b
3、实现一个随机样本产生器
4、把方法a和方法b跑相同的随机样本,看看得到的结果是否一样
5、如果有一个随机样本使得比对结果不一样,打印样本进行人工干预,改进方法a和方法b
6、当样本数量很多时对比测试依然正确,可以确定方法a已经正确

例如:

public class Code03_InsertionSort {

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

	// i和j是一个位置的话,会出错
	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];
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test
	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 < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) 
					- (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// 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();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100; // 随机数组的长度0~100
		int maxValue = 100;// 值:-100~100
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			insertionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				// 打印arr1
				// 打印arr2
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		insertionSort(arr);
		printArray(arr);
	}

}

二分法

经常见到的类型是在一个有序数组上开展二分搜索,但有序真的是所有问题求解时使用二分的必要条件么?
当然不是,只要能够正确构建左右两侧的淘汰逻辑,就可以二分

1、认识二分法
a、在一个有序数组中,找某个数是否存在

public class Code04_BSExist {

	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;
		// L..R
		while (L < R) {
			// mid = (L+R) / 2;
			// L 10亿  R 18亿
			// mid = L + (R - L) / 2
			// N / 2    N >> 1
			mid = L + ((R - L) >> 1); // mid = (L + R) / 2
			if (sortedArr[mid] == num) {
				return true;
			} else if (sortedArr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return sortedArr[L] == num;
	}

}

b、在一个有序数组中,找大于等于某个数最左侧的位置

public class Code05_BSNearLeft {

	// 在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;
	}

	// for test
	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) != nearestIndex(arr, value)) {
				printArray(arr);
				System.out.println(value);
				System.out.println(test(arr, value));
				System.out.println(nearestIndex(arr, value));
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

}

c、在一个有序数组中,找小于等于某个数最右侧的位置

public class Code05_BSNearRight {

	// 在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;
				L = mid + 1;
			} else {
				R = mid - 1;
			}
		}
		return index;
	}

	// for test
	public static int test(int[] arr, int value) {
		for (int i = arr.length - 1; i >= 0; 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) != nearestIndex(arr, value)) {
				printArray(arr);
				System.out.println(value);
				System.out.println(test(arr, value));
				System.out.println(nearestIndex(arr, value));
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

}

d、局部最小值问题

public class Code06_BSAwesome {

	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;
			}
		}
		return left;
	}

}

异或运算

介绍:

异或运算:相同为1,不同为1
同或运算:相同为1,不同为0
所以:异或运算记为无进位相加。

性质:

0^N == N N^N==0
异或运算满足交换律和结合律

异或题目

1、一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数

根据异或原理 当N^N == 0,把数组中所有的数进行异或操作,偶数次的值异或的结果是0,0^N=N的公式得出,异或出的值就是那个出现奇数次的值

// arr中,只有一种数,出现奇数次
	public static void printOddTimesNum1(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		System.out.println(eor);
	}

2、怎么把一个int类型的数,提取出最右侧的1来

N & ((~N )+ 1)

	public static int bit1counts(int N) {
		int count = 0;
		
		//   011011010000
		//   000000010000     1
		
		//   011011000000
		// 
		
		
		
		while(N != 0) {
			int rightOne = N & ((~N) + 1);
			count++;
			N ^= rightOne;
			// N -= rightOne
		}
		
		
		return count;
		
	}

3、一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这个数

// arr中,有两种数,出现奇数次
	public static void printOddTimesNum2(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		// eor = a ^ b
		// eor != 0
		// eor必然有一个位置上是1
		// 0110010000
		// 0000010000
		int rightOne = eor & (~eor + 1); // 提取出最右的1
		int onlyOne = 0; // eor'
		for (int i = 0 ; i < arr.length;i++) {
			//  arr[1] =  111100011110000
			// rightOne=  000000000010000
			if ((arr[i] & rightOne) != 0) {
				onlyOne ^= arr[i];
			}
		}
		System.out.println(onlyOne + " " + (eor ^ onlyOne));
	}