LeetCode_各种排序算法和查找算法

数据结构

算法

算法性能评估
时间和空间复杂度分析

时间复杂度分析：

上面的程序：时间复杂度为O(n)。

对数事件复杂度：上面程序的时间复杂度为O(log3n)~ O(logn)



空间复杂度
常量阶：O(1)
线性阶：O(n)

排序算法
冒泡排序，选择排序，归并排序，插入排序，快速排序，桶排序
主要记住冒泡排序和归并排序
当数据规模超过10000，我们就不应该考虑O(N*N)规模的算法

1:冒泡排序
时间复杂度：O(n*n)

2:选择排序
时间复杂度：O(n*n)

3:归并排序
时间复杂度：O(nlogn)

题目：

class Solution {
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        #上面的代码是归的过程
        #下面的代码是并过程
        int i = l, j = mid + 1;
        int cnt = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[cnt++] = nums[i++];
            } else {
                tmp[cnt++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[cnt++] = nums[i++];
        }
        while (j <= r) {
            tmp[cnt++] = nums[j++];
        }
        for (int k = 0; k < r - l + 1; ++k) {
            nums[k + l] = tmp[k];
        }
    }
}

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

4:插入排序
时间复杂度：O(n)


5:快速排序
时间复杂度：O(nlogn)
空间复杂度：O(logn)

找一个分区点，按照分区点分区。

6:桶排序
时间复杂度：O(nlongm/n)

Java内置排序
对基本数据类型进行排序
Arrays.sort()

对引用类型数据进行排序

对于动态数组的排序
Collections.sort(list)

对于O(n*n)时间复杂度排序，选择插入排序。对于O(nlongn)时间复杂度，选择归并排序。

二叉树：

前中后序遍历可以考虑使用递归的方法。
层次遍历：如何确定当前数是第几层

if(res.size() == level){
     List<Integer> val1 = new ArrayList<Integer>();
       val1.add(root.val);
       res.add(val1);
     }else{
      res.get(level).add(root.val);

        }
1
2
3
4
5
6
7
8

Queue<TreeNode> queue = new LinkedList<>();
int level = 0;
while(!queue.isEmpty()){
   int size = queue.size();
   for(int i=0;i<size;i++){
    TreeNode curr = queue.poll();
    if(curr.left != null) queue.offer(curr.left);
    if(curr.right!= null) queue.offer(curr.right);
   }
   level++;
}
1
2
3
4
5
6
7
8
9
10
11

DFS：因为先进后出的思想，所以需要利用栈来实现
BFS：因为先进先出的思想，所以需要利用队列来实现

动态规划：

主要是解决最优值问题

四个步骤：
1:定义状态数组
2:状态初始化
3:编写状态转移方程
4:返回最终需要的状态值

硬币找零问题：

填表法：

记忆化搜索

记忆化搜索代码：

class Solution {
    public Map<Integer,Integer> mapset = new HashMap<Integer,Integer>();
    public int fib(int n) {
     if(n==0)return 0;
     if(n==1)return 1;
     if(mapset.containsKey(n)){
         return mapset.get(n);
     }
     int sum = fib(n-1) + fib(n-2);
      mapset.put(n,sum);
     return sum ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

查找算法

线性查找：对于一个无序的数组采用线性查找。
二分查找：对于有序的数组采用二分查找。