数据结构01

Posted on Edited on In Views:

基本概念

什么是数据结构？

以某种特定的布局存储数据，以便高效操作。

时间复杂度：

对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：

是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

常用的数据结构

  • 数组
  • 堆栈
  • 队列
  • 链表
  • 树
  • 图
  • 字典树（Tries，这是一种高效的树，有必要单独列出来）
  • 哈希表

数组

  • 堆栈和队列都源自数组。
  • 一维数组
  • 多维数组

数组的基本操作

  • Insert——在给定索引位置插入一个元素
  • Get——返回给定索引位置的元素
  • Delete——删除给定索引位置的元素
  • Size——获取数组内所有元素的总数

常问的数组面试问题：

找到数组中第二小的元素

  • 一次遍历中找到最小的两个数，时间复杂度为O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 一次遍历中找到最小的两个数，时间复杂度为O(n) <br>
     * {1,1,2} will return 1.
     * @param array
     */
    public static int get2ndMinNumber(int[] array) {
    	int firstMin = Integer.MAX_VALUE;
    	int secondMin = Integer.MAX_VALUE;
    	for (int i = 0; i < array.length; i++) {
    		if (firstMin > array[i]) {
    			secondMin = firstMin;
    			firstMin = array[i];
    		} else {
    			if (secondMin > array[i]) {
    				secondMin = array[i];
    			}
    		}
    	}
    	return secondMin;
    }

找到数组中第一个没有重复的整数

  • 时间复杂度为O(n^2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 时间复杂度为O(n^2)
     */
    public static int get1stNonDuplicateNumber(int[] array) {
    	for (int i = 0; i < array.length; i++) {
    		int a =  array[i];
    		for (int j = 0; j < array.length; j++) {
    			if (i!=j) {
    				int b = array[j];
    				if (a==b) {
    					break;
    				}
    			}
    			if (j==array.length-1) {
    				return a;
    			}
    		}
    	}
    	return 0;
    }

  • 时间复杂度为O(n)，需要辅助的空间复杂度O(n)。

  • DONE: Space Complexity

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

    /**
     * 放入Map中统计每个元素的重复次数 <br>
     * LinkedHashMap guarantee insert order<br>
     * 时间复杂度为O(n)，需要辅助的空间复杂度O(n)。
     */
    public static int get1stNonDuplicateNumber2(int[] array) {
    	Map<Integer, Integer> map = new LinkedHashMap<>();
    	for (int i = 0; i < array.length; i++) {
    		if (map.containsKey(array[i])) {
    			map.put(array[i], map.get(array[i])+1);
    		} else {
    			map.put(array[i], 1);
    		}
    	}
    	for (Entry<Integer, Integer> entry : map.entrySet()) {
    		if (entry.getValue()==1) {
    			return entry.getKey();
    		}
    	}
    	return 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
58
59
/**
 * 采用分治法（Divide and Conquer）<br>
 * 把长度为n的输入序列分成两个长度为n/2的子序列 <br>
 * 对这两个子序列分别采用归并排序；<br>
 * 将两个排序好的子序列合并成一个最终的排序序列。<br>
 */
public static int[] mergeSort(int[] array) {
	if (array.length<2) {
		return array;
	}
	int middle = array.length%2==0? array.length/2 : (array.length-1)/2; 
	int[] left =  Arrays.copyOfRange(array, 0, middle);
	int[] right =  Arrays.copyOfRange(array, middle, array.length);
	return merge(mergeSort(left),mergeSort(right));
}

/**
 * 正序。合并两个有序数组。
 * @param left
 * @param right
 * @return
 */
public static int[] merge(int[] left, int[] right) {
	int[] result = new int[left.length+right.length];
	int resultIndex = 0;
	int leftIndex = 0;
	int rightIndex = 0;
	while (left.length>leftIndex && right.length>rightIndex) {
		int smallerNumber;
		int leftNumber = left[leftIndex];
		int rightNumber = right[rightIndex];
		if (leftNumber < rightNumber) {
			smallerNumber = leftNumber;
			leftIndex++;
		} else {
			smallerNumber = rightNumber;
			rightIndex++;
		}
		result[resultIndex] = smallerNumber;
		resultIndex++;
	}
	
	// 当其中一个数组到头的时候，另一个数组全部加到尾部
	if (left.length==leftIndex) {
		while (rightIndex<right.length) {
			result[resultIndex] = right[rightIndex];
			resultIndex++;
			rightIndex++;
		}
	} else {
		while (leftIndex<left.length) {
			result[resultIndex] = left[leftIndex];
			resultIndex++;
			leftIndex++;
		}
	}
	
	return result;
}

重新排列数组中的正值和负值

  • 冒泡算法，依次比较相邻的两位，满足条件就交换位置
    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
    /**
     * -3 4 2 -1 7 3 -5 ->
     * -3 -1 -5 4 2 7 3
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
    	/*
    	 * j i -3 4 2 -1 7 3 -5
    	 * 6 0 -3 4 2 -1 7 3 -5
    	 * 6 1 -3 4 2 -1 7 3 -5
    	 * 6 2 -3 4 -1 2 7 3 -5
    	 * 6 3 -3 4 -1 2 7 3 -5
    	 * 6 4 -3 4 -1 2 7 3 -5
    	 * 6 5 -3 4 -1 2 7 -5 3
    	 * 
    	 * 5 0 -3 4 -1 2 7 -5 3
    	 * 5 1 -3 -1 4 2 7 -5 3
    	 * 5 2 -3 -1 4 2 7 -5 3
    	 * 5 3 -3 -1 4 2 7 -5 3
    	 * 5 4 -3 -1 4 2 -5 7 3
    	 * 
    	 * 4 0 -3 -1 4 2 -5 7 3
    	 * 4 1 -3 -1 4 2 -5 7 3
    	 * 4 2 -3 -1 4 2 -5 7 3
    	 * 4 3 -3 -1 4 -5 2 7 3
    	 * 
    	 * 3 0 -3 -1 4 -5 2 7 3
    	 * 3 1 -3 -1 4 -5 2 7 3
    	 * 3 2 -3 -1 -5 4 2 7 3
    	 */
    	for (int j = array.length-1; j > 0; j--) {
    		for (int i = 0; i < j; i++) {
    			int a = array[i];
    			int b = array[i+1];
    			if (a>=0 && b<0) {
    				array[i] = b;
    				array[i+1] = a;
    			}
    		}
    	}
    	return array;
    }

堆栈

一堆垂直排列的书籍。为了获得位于中间位置的书，你需要拿掉放在它上面的所有书籍。这就是 LIFO（后进先出）方法的工作原理。
堆栈的基本操作：

  • Push——在顶部插入元素
  • Pop—— 从堆栈中删除后返回顶部元素
  • isEmpty——如果堆栈为空，则返回 true
  • Top ——返回顶部元素，但不从堆栈中删除

队列

First in First Out。排队买票。
队列的基本操作：

  • Enqueue() —— 向队列末尾插入元素
  • Dequeue() —— 从队列头部移除元素
  • isEmpty() —— 如果队列为空，则返回 true
  • Top() —— 返回队列的第一个元素

链表

  • Head->[data|pointer]->[data|pointer]->null

图

一组节点，以网络的形式互相连接。

树

树是一种层级数据结构，包含了连接它们的节点和边。
树的基本术语

  • root
  • parent
  • child
  • leaf
  • sibling

二叉树

高度

两种定义：

  • 从根节点到最深节点的最长路径的节点数。
  • 从根到最深节点的最长路径的边数。

两种算法：

  • 层级遍历法
  • 递归法。

层级遍历法 - 获取二叉树的高度

主要步骤是：

  • 创建空队列保存二叉树的每一层节点
  • 初始化标识二叉树高度的变量height为0
  • 一层一层地遍历二叉树，每向下遍历一层，高度height加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
    /**
     * 使用迭代方式，时间复杂度O(n)
     * - add all the nodes of current level to the queue <br》
     * - if queue size > 0 , height++ <br>
     * - remove each nodes of queue, and add its children into queue <br>
     * - until queue size = 0
     * @param root
     * @return height
     */
    public static int getHeight(TreeNode root) {
    	int height = 0;
    	
    	// to store nodes for each level
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.add(root);
    	
    	while (queue.size()>0) {
    		// get number of nodes for this level
    		int nodeCount = queue.size();
    		if (nodeCount == 0) {
    			break;
    		}
    		
    		height++;
    		
    		while (nodeCount>0) {
    			TreeNode node = queue.remove();
    			if (leftOf(node)!=null) {
    				queue.add(leftOf(node));
    			}
    			if (rightOf(node)!=null) {
    				queue.add(rightOf(node));
    			}
    			nodeCount--;
    		}
    	}
    	return height;
    }

递归法 - 获取二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
/**
 * 使用递归，时间复杂度O(n)
 * @param root
 * @return
 */
public static int getHeight2(TreeNode node) {
	if (node!=null) {
		return Math.max(getHeight2(leftOf(node)), getHeight2(rightOf(node)))+1;
	}
	return 0;
}

找到一个二叉树中给定节点的祖先（ancestors）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 使用递归，找到一个二叉树中给定节点的祖先, 时间复杂度O(n)
 * @param node
 * @return
 */
public static List<TreeNode> getAncestors(TreeNode node){
	List<TreeNode> nodes = new ArrayList<>();
	TreeNode father = node.getParent(); 
	if (father!=null) {
		nodes.add(father);
		nodes.addAll(getAncestors(father));
	}
	return nodes;
}

二叉搜索树

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

寻找二叉搜索树中第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
/**
 * 中序遍历 get Kth Smallest Element in a BST
 * @param root
 * @return
 */
public static IntBSTNode getKthSmallestNode(IntBSTNode root, int k) {
	
	// store all elements into a ordered list
	List<IntBSTNode> nodes = new ArrayList<>();
	inOrder(root, nodes);
	return nodes.get(k-1);
}

/**
 * 中序遍历
 * @param node
 * @param nodes
 */
private static void inOrder(IntBSTNode node, List<IntBSTNode> nodes) {
	if (node==null) {
		return;
	}
	inOrder(node.getLeft(), nodes);
	nodes.add(node);
	inOrder(node.getRight(), nodes); 
}

递归（计算节点数量）：

  • 如果是当前节点，返回。
  • 如果左边总数+1（当前节点）小于k，答案是右边第（k-（左边总数+1））小的数。
  • 如果左边总数+1（当前节点）大于k，答案是左边第k小的数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 递归（计算节点数量）：
     */
    public static IntBSTNode getKthSmallestNode2(IntBSTNode root, int k) {
    	int leftCount = countNode(root.getLeft());
    	if (leftCount==k-1) {
    		return root;
    	} else if(leftCount<k-1) {
    		return getKthSmallestNode(root.getRight(), k-leftCount-1);
    	} else {
    		return getKthSmallestNode2(root.getLeft(), k);
    	}
    }

    public static int countNode(IntBSTNode node) {
    	if (node==null) {
    		return 0;
    	}
    	return 1+countNode(node.getLeft())+countNode(node.getRight());
    }

字典树（Tries，这是一种高效的树）

top,thus,their