查找最大子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * 分析：一个最大子序列必然不可能以一个负数a[i]开头，否则子序列可以以a[i+1]开头
 * 推广，一个子序列比不可能以一个he为负数的子序列开头，否则这段子序列可以去除
 * 推论，一个最大子序列的任意子序列必然和为正，因此和为负的子序列可以舍弃
 * 推论，任意和不为负的子序列都可以作为最大子序列的前子序列
 */
public static int maxSubSequenceSum(int[] a){
		int maxSum = 0; int thisSum = 0;
		for(int i = 0;i<a.length;i++){
			thisSum+=a[i];
			if(thisSum>maxSum){        //子序列不为负，可能成为最大子序列，比较并更新
				maxSum = thisSum; 
			}else if(thisSum<0){
				thisSum = 0;      //子序列和为负，不可能成为最大子序列的前子序列，舍弃
			}
		}
		return maxSum;
}

有序向量的唯一化（去除重复元素）

低效方法：

逐一比较相邻元素，删除重复中的后者。

1
2
3
4
5
6
7
8
9
public void removeDuplicate(Vector<Integer> s){
		int i = 0;
		while(i<s.size()-1){
			if(s.get(i).intValue()==s.get(i+1).intValue()){
				s.remove(i+1);
				i++;
			}
		}
	}

对于每一次remove操作都需要对后置位元素进行复制操作，最坏的情况是所有的元素都是相等的，那么时间复杂度将达到(n-2)+(n-3)+···+2+1=o(n^2)

高效方法：

逐一扫描，直至遇到不相同的元素，将其移至紧靠于前者后侧，然后删除多余元素。

1
2
3
4
5
6
7
8
9
public void removeDuplicate(Vector<Integer> s){
	int i = 0,j = 0;
	while(++j<s.size()){
		if(s.get(i).intValue()!=s.get(j).intValue()){
			s.set(++i, s.get(j));
		}
	}
	List<Integer> list = s.subList(0, i);
}

时间复杂度为 3*(n-1) = o(n)

由此可见，算法效率大大提升

有序向量查找（二分查找）

优化，不一定以中点为划分，这里略

排序

  • 冒泡排序，时间复杂度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
public static void mergeSort(int[] a, int lo, int hi) {
		if (hi<=lo)
			return;
		int mi = (lo + hi) / 2;
		mergeSort(a, lo, mi);
		mergeSort(a, mi+1, hi);
		merge(a, lo, mi, hi);
}
public static void merge(int[] a, int lo, int mi, int hi) {
	int c[] = new int[hi - lo + 1];
	int m = 0;
	for (int i = lo, j = mi+1;!(i > mi && j > hi);) {
		if (i > mi) {
			c[m++] = a[j++];
		} else if (j > hi) {
			c[m++] = a[i++];
		} else if (a[i] >= a[j]) {
			c[m++] = a[j++];
		} else {
			c[m++] = a[i++];
		}
	}
	for (int i = 0, j = lo; i < c.length;) {
		a[j++] = c[i++];
	}
}