数据算法与结构

常数操作

和数据量无关的，固定时间的操作是常数操作，叫做 big O （字母O） 指的是上限的意识，也就是最耗时间，最差的情况

加减乘除和位运算，数组的寻址等都是常数操作，链表找第N个元素不是常数操作

log：以 2 为底
lg ： 以 10 为底
ln ： 以 e 为底

时间复杂度

常数表达式中（按最差的情况估计），只要高阶项，不要低阶项，并且忽略高阶项系数的表达式

还有两种时间复杂度表达式是平均时间复杂度O中间一横线，最好的情况的时间复杂度，欧姆的符号

如 aN^2 + bN^2 + c 时间复杂度位 O(N^2)

评价一个算法流程的好坏，先看时间复杂度指标，然后再分析不同数据样本下的实际运行时间，也就是‘常数项时间’

O(logN)=O(log2N) 默认以2为底 省略不写，如果以其他数字比如3为底 就不能省略O(log3N)

额外空间复杂度

有 O(1)表示空间是固定大小，与数据量样本无关 ， O(N)

亦或运算

相同为0，不同为1，不进位相加

• 性质1
  • 0^N=N：0 亦或任何数，得到这个数本身，
  • N^N=0： 任何数亦或自己，得到0，
• 性质2
  • 满足交换律和结合律，（用无进位相加来解释）
    • a^b=b^a
    • (a^b)^c=a^(b^c)
• 性质3
  • 由上两条得出任意个数的数字进行亦或，谁先谁后结果都是相同

题目：

1. 在一个数组中，一种数出现了奇数次，其他数都出现偶数次，求这个出现奇数次的数字？

   全部数进行亦或得到eor

2. 在一个数组中，两种数出现了奇数次，其他数都出现偶数次，求这两个个出现奇数次的数字？

   设这两个数为 a，b， a!=b, 用eor亦或全部数得到 eor=a^b 因为a != b, 所以eor != 0， 所以eor 二进制位肯定有一位是1，求出eor最后一个位置的提取最低位的1，假设是第8位，那么a和b第八位上肯定分别为1和0

   再用eor1 去亦或所以的数字，但是只亦或第8位为0 （1也可以）的数字，目的是排除a 或b（求出eor最后一个为1的二进制位是为了区分a和b），当然排除了其他数字也没关系，因为其他数字出现偶数次不影响结果，得到eor1 等于a 或者b

   现在有eor=a^b, 又有eor1等于其中一个数，那么 eor^eor1等于另一个数

   然后遍历数组中的元素e 用 x=e^c=e^a^b 向后遍历数组e1，如果存在e1==x，那么 a=e， b=e1=x

// 使用亦或进行数组元素交换时，切勿交换同一位置，否则该位置的值 置为0了

        int[] arr = {50, 60};
        int i = 0;
        int j = 0;
        arr[i] = arr [i] ^ arr[j];
        arr[j] = arr [i] ^ arr[j];
        arr[i] = arr [i] ^ arr[j];
        //两个下标指向数组同一位置，交换后，该位置数值变成了0
        System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr));// [0, 60]

// 如果使用亦或进行两数交换，这两个数必须为两块空间，否则结果变成了0		
		int a = 17;
        int b = a; // 可以完成交换，b是新开辟的空间，并不是指向a，java中基本类型变量中存的永远是值，而不是引用指针
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("a = " + a);
        System.out.println("b = " + b);
        class Num {
            int n;

            Num(int n) {
                this.n = n;
            }
            int get() {return n;}
            void set(int n) {this.n = n;}
        }
// 引用对象中的同一位置进行交换 置0 错误示例
        Num n1 = new Num(17);
        Num n2 = new Num(17); // Num n2 = n1; 如果指向同一块区域将无法完成交换并且操作后不管原先值是多少值变成了0
        n1.set(n1.get() ^ n2.get());
        n2.set(n1.get() ^ n2.get());
        n1.set(n1.get() ^ n2.get());
        System.out.println("n1.get() = " + n1.get());
        System.out.println("n2.get() = " + n2.get());

二进制位 完全二叉树或者是近似完全二叉树。

二叉堆每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

二叉堆排序的思路：遍历未排序的数组，将数组中的每个数放入二叉堆中，再将堆顶元素弹出直至为空。

向二叉堆中添加元素：可将新的元素添加至最后一个叶子节点旁，与其父节点比较，逐渐上浮，即swim() 方法

弹出二叉堆堆顶元素：获得堆顶元素后，可将二叉堆最后一个叶子节点替换掉堆顶元素，将新的堆顶元素下沉至合适的位置，即sink() 方法。

用数组表示二叉堆：由于二叉堆是一个完全二叉树，因此可以采用层序遍历的方式将二叉堆存储在数组中，其中arr[0] 是堆顶元素，对于任意的arr[i]，其父节点为arr[(i-1)/2]，其左右子节点为 arr[2 * i + 1]，arr[2 * i + 2].

二叉堆深度为 log(n)

时间复杂度 O(nlogn)

空间复杂度 O(n)

局部最小

一个数组中，任意一个数与相邻数不相等，如果这个数比两边数都小，那么这个数就是局部最小，两边的数只要判断相邻的一个数即可

如果0位置比1位置大， n-1 位置比n-2位置大，那么0到n-1位置一定存在局部最小，可以画折线图证明

查找局部最小：首先判断两端，如果没有，那么去中间的点m，如果m不是局部最小，一定存在m-1 或m+1 比m 小，如果m-1比m小，那么0到m-1一定存在局部最小，二分查找依次类推。

对数器

1.有一个你想要测的方法a；
2.实现一个绝对正确但是复杂度不好的方法b；
3.实现一个随机样本产生器；
4.实现对比算法a和b的方法；
5.把方法a和方法b比对多次来验证方法a是否正确；
6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

求中点

方式1：(l+r)/2 加法可能会溢出

方式2: l+((r-l) >> 1) 右移一位相当于除以2

master公式

递归行为符合这样的公式 只要子规模满足等规模(就是子问题每次都是对半砍，或者1/3, 1/5都算)就可以使用master公式求解时间复杂度

T(N) = a*T(N/b) + O(N^d)

N:母问题的数据量

T(N/b) :子问题的规模，如果是等量的

a:子问题调用次数，如果子问题规模等量的情况下

O(N^d):除了子问题之外剩下的过程的时间复杂度

// 求数组最大值
public static int process(int[] arr, int l, int r) {
    if(l == r) return arr[l];
    int mid = l + ((r - l) >> 1);
    int lMax = process(arr, l, mid);
    int rMax = process(arr, mid, r);
    return Math.max(lMax, rMax);
}
// 母问题数据量N
// 调用了两次子问题，所以a=2
// 每次子问题对半砍 所以，b=2 子问题规模为N/2，
// d=0, 其他过程时间复杂度为O(1)
// log(b,a) == log(2,2)==1 > d 所以得出时间复杂度为O(N)

a b d 三个系数确定后可以根据下面3个情况求得递归行为的时间复杂度

1. log(b,a) < d -> O(N^d)
2. log(b,a) = d -> O(N^d*log(N))
3. log(b,a) > d -> O(N^log(b,a))

贪心算法