刷题基础知识

时间复杂度

基本题目要求都是1s内完成。根据不同复杂度对应的n值（基于测评机器的算力）

复杂度	N值
$O(log(N))$	$10^{20}$
$O(N^{\frac{1}{2}})$	$10^{16}$
$O(N)$	$10^8$
$O(Nlog(N))$	$10^6$
$O(N^2)$	$10^4$
$O(N^3)$	$400$
$O(N^4)$	100
$O(2^N)$	26
$O(N!)$	11

注：intel ultra200的CPU算力是 $15TOPS\approx10^{13}$，对应的$O(N)=10^{13}$。

数组复制

Arrays.copyOf：由Arrays类提供

public static <T> T[] copyOf(T[] original, int newLength)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)

int[] original = {1, 2, 3, 4, 5};
int[] copied = Arrays.copyOf(original, 3);

其中original可以是泛型类数组：

void method(T[] arr){
    T[] newArr = Arrays.copyOf(arr, arr.length)
}

System.arraycopy：是本地方法，更底层效率更高。

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

int[] original = {1, 2, 3, 4, 5};
int[] copied = new int[3];
System.arraycopy(original, 2, copied, 0, 3);
// copied = {3, 4, 5}

数组排序

• 对象数组：让对象实现Comparable接口，并重写compareTo()方法。

• 基本类型数组：向Arrays.sort传入Comparator接口

• Arrays.sor 和 Collections.sort() 都是在原数组上排序（Collections.sort()本质使用了Arrays.sort()）

int[][] points;
Arrays.sort(points, (o1, o2) -> {
        if (o1[1] != o2[1]) {
            return Integer.compare(o1[1], o2[1]);
        } else {
            return Integer.compare(o1[0], o2[0]);
        }
    });