leetcode基础算法

发表于 | 分类于

排序算法

算法 稳定性 时间复杂度 空间复杂度 备注
选择排序 × N^2 1
冒泡排序 √ N^2 1
插入排序 √ N ~ N^2 1 时间复杂度和初始顺序有关
希尔排序 × N 的若干倍乘于递增序列的长度 1 改进版插入排序
快速排序 × NlogN logN
三向切分快速排序 × N ~ NlogN logN 适用于有大量重复主键
归并排序 √ NlogN N
堆排序 × NlogN 1 无法利用局部性原理

快速排序

快排的最坏时间复杂度，选的初始值是最大值或者是最小值，这样就是N-1+N-2+….1=O(n^2).

最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况,就是二叉树的层数

最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
  /*
     * 1.确定分界点(nums[l],nums[r],nums[(l+r)/2])
     * 2.调整区间，左区间<=x,右区间>=x
     *       使用两个指针来实现，一个指向头，一个指向尾部，假如分界点取nums[i]，那么尾部指针先动，走向中间
     *       当某个数<x，该指针停止，头部指针开始往中间走，当某个数>x,停止，将尾部指针指向的<x的数与头部指向的数交换
     *       就可以达到目的，直到两个指针相遇
     *
     * 3.递归左右两个子区间
     * */
public void quick_sort(int nums[],int l,int r){
    if(l>=r)
        return ;
    int left = l-1,right = r+1;
    int base = nums[(l+r)>>1];
    while(left<right){
        do{
            left++;
        }while(nums[left]<base);

        do{
            right++;
        }while(nums[right]>base);
        if(left<right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }
    //进行递归，分别判断左右两个子区间
    quick_sort(nums,l,right);
    quick_sort(nums,right+1,r);
}

改进版的快速排序，分为<num等于num以及大于num三个子区间，这样的话当数据中有大量相同的数据，就可以大大节省时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void quick_sort2(int[] nums,int left,int right){
    if(left>=right){
        return ;
    }
    int mid = (left+right)/2;
    //拆分为三个子区间
    int less =left-1;
    int more = right +1;
    int cur = left;
    int target = nums[mid];
    while(cur!=more){
        if(nums[cur]<target){
            less++;
            swap(nums,cur,less);
            cur++;
        }else if(nums[cur]>target){
            more--;
            swap(nums,cur,more);

        }else{
            cur++;
        }
    }

    if(less>left) {
        quick_sort2(nums, left, less);
    }
    if(more<right) {
        quick_sort2(nums, more, right);
    }
}

75.荷兰国旗问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
     * 其实就是< num放左边，==num放中间,>num放右边的问题
     * 准备三个指针，less表示小于num的临界指针，cur当前元素的指针，大于num表示大于num的临界指针
     * 当nums[cur]<target，将当前值与less临界指针阿下一个元素交换，less指针后移，cur后移
     * 当nums[cur]==target，cur后移，无其它操作
     * 当nums[cur]>target，将该元素与more指针的前一个元素交换,more前移
     * */
public void sortColors(int[] nums) {
    if(nums.length<2){
        return;
    }
    int target = 1;
    //定义指针，<num为-1，>num为nums.length，cur==0
    int less =-1;
    int cur = 0;
    int more = nums.length;
    while(cur!=more){
        if(nums[cur]<target){
            swap(nums,cur,less+1);
            less++;
            cur++;
        }else if(nums[cur]==target){
            cur++;
        }else{
            swap(nums,cur,more-1);
            more--;
            //注意，不需要cur++，因为交换的cur实际上可能<target
            // cur++;
        }
    }
}
public void swap(int[] arr,int a,int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

归并排序

合二为一。将两个排序好的数组进行合并，使用双指针。

空间复杂度：O(N)，即tmp数组

时间复杂度：O(nlogN)，可有公式求出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
     * 1.确定分界点，取mid
     * 2.递归排序左右两个子区间
     * 3.归并两个排完序的子区间，使用双指针来解决
     * */
public static void merge_sort(int[] nums,int l,int r){
    if(l>=r)
        return;
    int mid = (l+r)>>1;
    //递归排序
    merge_sort(nums,l,mid);
    merge_sort(nums,mid+1,r);
    //临时存储合并的排序结果
    int[] tmp = new int[r-l+1];
    int index = 0;
    int first = l;
    int second = mid+1;
    while(first<=mid&&second<=r){
        if(nums[first]<=nums[second]){
            tmp[index++] = nums[first++];
        }else{
            tmp[index++] = nums[second++];
        }
    }

    while(first<=mid){
        tmp[index++] = nums[first++];
    }
    while(second<=r){
        tmp[index++] = nums[second++];
    }
    //将临时数组内容存储到nums中
    int j = 0;
    for(int i = l;i<=r;i++){
        nums[i] = tmp[j++];
    }
}

小和问题

主要借助归并排序来解决。类似于可以划分为左右子区间的问题都可以使用递归方式来解决。

1576392749776

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static int merge(int[] arr,int left ,int right){
    int mid = left+((right-left)>>1);
    if(left>=right){
        return 0;
    }
    int left_result = merge(arr,left,mid);
    int right_result = merge(arr,mid+1,right);
    //合并
    int[] tmp = new int[right-left+1];
    int index = 0;
    int first = left;
    int secod = mid+1;
    int res = 0;
    //对排完序的左右子区间进行合并操作
    //需要注意的是，假如左子区间的某个数i<右子区间的某一个数j，这个数必定就是右子区间j以及j之后的数的小数，因为两个子区间都是有序的
    while(first<=mid&&secod<=right){
        if(arr[first]<arr[secod]){
            res += (right-secod+1)*arr[first];
            tmp[index++] = arr[first++];
        }else{
            tmp[index++] = arr[secod++];
        }
    }
    while(first<=mid){
        tmp[index++] = arr[first++];
    }
    while(secod<=right){
        tmp[index++] = arr[secod++];
    }
    index = 0;
    for(int i=left;i<=right;i++){
        arr[i] = tmp[index++];
    }
    //结果为两区间之和+合并区间
    return left_result+right_result+res;

}

冒泡排序

时间复杂度为O(n^2)。n-1+n-2+….2=n^2/2

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

每一次循环都会有一个位置的元素确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] arr){
    if(arr==null||arr.length<2){
        return;
    }
    for(int i=0;i<arr.length;i++){
        for(int j=i+1;j<arr.length;j++){
            if(arr[i]>arr[j]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

选择排序

与冒泡排序差不多,与冒泡排序最大的区别就就是它的交换元素每一次只交换一次，选择排序是不稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectSort(int[] arr){
    if(arr==null||arr.length<2){
        return;
    }
    int minindex = 0;
    for(int i = 0;i<arr.length;i++){
        minindex = i;
        for(int j = i+1;j<arr.length;j++){
            if(arr[j]<arr[minindex]){
                minindex = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minindex];
        arr[minindex] = tmp;
    }
}

插入排序

时间复杂度最差是O(n^2)，逆序的情况下，最好是O(n)，顺序的情况下。

1
2
3
4
5
6
7
8
9
10
public void insertSort(int[] arr){
    for(int i=1;i<arr.length;i++){
        int j=i-1;
        while(j>=0&&arr[i]>arr[j]){
            swap(arr,i,j);
            i =j;
            j=j-1;
        }
    }
}

堆排序

堆结构

堆的插入删除时间复杂度是logN，即树的高度，因此，效率很高。

堆实际上是一个完全二叉树，堆可以用数组来表示，位置 k 的节点的父节点位置为 （k-1）/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

大顶堆：父节点的值大于他所有子孙的值。

小顶堆：父节点的值小于他所有子孙的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//上浮操作
//与祖先节点进行比较，假如小于祖先节点，那么替换掉祖先节点,某个点父节点为(i-1)/2
public void heapInsert(int[] arr,int i){
    while(arr[i]>arr[(i-1)/2]){
        swap(arr,i,(i-1)/2);
        i = (i-1)/2;
    }
}

//下沉操作
//heapsize为边界
public void heapify(int[] arr,int i,int heapsize){
    //i的左节点
    int left = i*2+1;
    //假如该节点它的某个子孙节点小，那么，就将二者交换
    while(left <= heapsize){
        //获取左右节点最大值
        int right = left+1;
        int largest = 0;
        if(right<=heapsize){
            largest = arr[right]>arr[left]?right:left;
        }else {
            largest = left;
        }
        //该节点与其孩子节点进行比较
        largest = arr[i]>arr[largest]?i:largest;
        //假如该节点大于其左右孩子，那么直接结束循环
        if(largest==i){
            break;
        }
        //该节点小于左或者右孩子，进行交换，继续循环
        swap(arr,i,largest);
        i = largest;
        left = i*2+1;
    }
}

/**
     * 1.构建堆，通过上浮来完成
     * 2.从构建好的堆中取根节点，并将最后一个节点填补上来
     * */
public void heapSort(int[] arr){
    //构建堆
    for(int i=0;i<arr.length;i++){
        heapInsert(arr,i);
    }
    //取节点
    int heapsize = arr.length-1;
    while(heapsize>0){
        swap(arr,0,heapsize);
        heapsize--;
        heapify(arr,0,heapsize);
    }
    if (arr == null || arr.length < 2) {
        return;
    }
}

非基于比较器的排序

桶排序，基数排序，计数排序。

1576392783112

采用桶的思想来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
     * 假如数组有n个元素，那么准备n+1个桶
     * 遍历一次数组，求出最大值最小值，将各个桶按照最大值最小值均分，比如，min=0,max=99，则桶为0~9,10~19.....90~99
     * 这样的话，第一个桶必定有一个元素，即最小值，最后一个桶必定会有一个最大值
     * 因此，需要将n-2个元素插入剩下的n+1个桶中，这样必定至少会有一个空桶
     * 这样的话，空桶的左右两侧肯定各有一个非空桶，这样的话，最大差值一定不可能在桶内元素，而是在桶间元素
     * 因此，我们只需要记录各个桶的最大值最小值，然后跨桶的最小值-最大值中必定含有最大差值
     * */
public int maxGap(int[] arr){
    if(arr==null||arr.length<2){
        return 0;
    }
    int length = arr.length;
    //寻找min max
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int i=0;i<length;i++){
        min = Math.min(min,arr[i]);
        max = Math.max(max,arr[i]);
    }
    if(min==max){
        return 0;
    }
    //桶是否有数据，各桶最大值，最小值
    boolean[] hasNum = new boolean[length+1];
    int[] maxs = new int[length+1];
    int[] mins = new int[length+1];
    int bucketNum=0;
    for(int i=0;i<length;i++){
        //计算属于哪一个桶
        bucketNum = getBucket(arr[i],length,min,max);
        //桶内最大值，最小值
        maxs[bucketNum] = hasNum[bucketNum]?Math.max(arr[i],maxs[bucketNum]):arr[i];
        mins[bucketNum] = hasNum[bucketNum]?Math.min(arr[i],mins[bucketNum]):arr[i];
        hasNum[bucketNum] = true;
    }
    //获取桶间元素最大值
    int maxBetweenBucket = 0;
    int lastMax = maxs[0];
    for(int i=1;i<length+1;i++){
        if(hasNum[i]) {
            maxBetweenBucket = mins[i] - lastMax > maxBetweenBucket ? (mins[i] - lastMax) : maxBetweenBucket;
            lastMax = maxs[i];
        }
    }
    return maxBetweenBucket;
}

递归程序时间复杂度计算

1576392803920

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * 后序遍历二叉树。
     * 左子树返回不为空，右子树返回不为空，则该node必定是公共祖先
     * */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //当前节点==p或者==q，那么该点必定是祖先
    if(root==null||root==p||root==q){
        return root;
    }
    //递归左右子树
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    TreeNode right = lowestCommonAncestor(root.right,p,q);
    //假如左右子树返回均不为空，那么当前节点就是公共祖先
    if(left!=null&&right!=null){
        return root;
    }
    //只有一个子树返回的不是空
    return left!=null?left:right;
}

该递归程序每次需要递归两次子区间，则a = 2，每个递归子区间大小是N/2，因此b = 2，而每次执行完还需要做O(1)的操作，因此，d= 0,log(b,a)=1>d,所以复杂度为O(N^log(2,2))=O(N)

工程中的排序算法

一般来说，是综合多种排序算法的。

假如数据量很小，使用插入排序；样本量很大，数据类型是基础类型，使用快排，数据类型是类，使用归并排序，可以保证数据稳定性。