算法概论作业2.1

发表于 | 分类于

##2.14

1
给定一个含有n个元素的数组，注意到数组中的某些元素是重复的，即这些元素在数组中出现不止一次。给出一种算法，以O（nlogn）时间移除掉数组中的所有重复元素。

###思路1：

1
先采用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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package homework_chen;

/**
 * 文 件 名 : test214.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月21日 
 * 描 述： 算法概论2.14题目源码
 */

public class test214 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] r = { 8, 6, 8, 0, 4, 2, 6, 8, 3, 2, 6, 2, 1, 2, 5, 8, 0, 6, 3, 1,
				2, 3, 5, 7, 9, 5, 8, 4, 8, 5, 7, 5, 6, 6, 3, 5, };
		System.out.println("排序前：");
		printarray(r);
		System.out.println("\n排序后");
		Merge_sort(r, 0, r.length - 1);
		printarray(r);
		removerepeat(r);
	}

	public static void printarray(int[] r) {
		for (int key : r)
			System.out.print(key + " ");
	}

	/**
	 * @param int []r 要求在线性时间内删除有序序列的重复元素
	 */
	public static void removerepeat(int[] r) {
		int[] tmp = new int[r.length];// 大小定义比较麻烦？不知道怎么定义大小？C++可以通过传递数组长度来约束，难道java也需要么？
		int k = 0;
		int t = Integer.MIN_VALUE;
		for (int i = 0; i < r.length; i++) {// 当不一样就加进去，前提是有序序列
			if (r[i] != t) {
				tmp[k++] = r[i];
				t = r[i];
			}
		}
		System.out.println("\n删除后：");// 输出结果，有必要可以在重建大小为k的数组，重新赋值并传出去
		for (int i = 0; i < k; i++)
			System.out.print(tmp[i] + " ");
	}

	/**
	 * @param int []r int start int mid int end 合并两段有序数组
	 * 在调用时开辟新空间，归并，最后赋值回来，java自带gc，无须回收
	 */
	public static void merge(int[] r, int start, int mid, int end) {
		int[] tmp = new int[end - start + 1];// 创建临时空间
		int k1 = start;// 记录第一有序序列的起始位置，
		int k2 = mid + 1;// 记录第一有序序列的起始位置，
		int k3 = 0;// 定义临时空间的起始位置
		while (k1 <= mid && k2 <= end) {// 当序列未到结尾时，归并
			if (r[k1] <= r[k2])// 若果第一个序列的值小于等于第二个，则把其存进临时数组
				tmp[k3++] = r[k1++];
			else
				tmp[k3++] = r[k2++];
		}
		// 当不满足while条件时，退出循环，此时将剩下的附在后面
		while (k1 <= mid)
			tmp[k3++] = r[k1++];
		while (k2 <= end)
			tmp[k3++] = r[k2++];
		// 全部完毕之后，将tmp回写到r数组中
		for (int i = 0; i < tmp.length; i++) {
			r[start++] = tmp[i];
		}
	}

	/**
	 * @param int []r int start int end 归并排序数组 当start < end 分割 分割完毕之后，相邻的合并
	 */
	public static void Merge_sort(int[] r, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			Merge_sort(r, start, mid);
			Merge_sort(r, mid + 1, end);
			merge(r, start, mid, end);
		}
	}
}

###思路2：

1
2
3
线性下找到数组的最大值，最小值，若相差距离可以接受，则此方法效率不错。然后建立hash数组，扫描r数组，若flag位置的值为false，则改为true，否则不变，最后再顺序扫描一遍hash数组，输出结果。
此方法为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
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
60
61
62
63
64
65
66
67
68
69
70
71
package homework_chen;

/**
 * 文 件 名 : test214.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.14题目源码new
 */

public class test214new {
	private static int max = Integer.MAX_VALUE;
	private static int min = Integer.MIN_VALUE;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] r = { 8, 6,  8, 0, 4, 2, 6, 8, 3, 2, 6, 2, 1, 2, 5, 8,
				0, 6, 3, 1, 2, 3, 5, 7, 9, 5, 8, 4, 8, 5, 7, 5, 6, 6, 3, 5, };
		fd_max_min(r);
		removerepeat(r, max, min);
	}

	/**
	 * @param int []r 找出r数组中的最大值，最小值，并赋值给全局变量
	 */
	public static void fd_max_min(int[] r) {
		for (int i = 0; i < r.length; i++) {
			if (r[i] > min)
				min = r[i];
			if (r[i] < max)
				max = r[i];
		}
		int t = min;
		min = max;
		max = t;// 交换
	}

	/**
	 * @param int []r 打印数组
	 */
	public static void printarray(int[] r) {
		for (int key : r)
			System.out.print(key + " ");
	}

	/**
	 * 
	 * @param r
	 * @param max
	 * @param min
	 * 用hash数组判定是否存在
	 */
	public static void removerepeat(int[] r, int max, int min) {
		int number = max - min + 1;
		boolean[] flag = new boolean[number];// 初始化为false
		for (int i = 0; i < r.length; i++) {
			int t = r[i] - min;
			if (flag[t] == false) {
				flag[t] = true;
			}
		}
		for (int i = 0; i < flag.length; i++) {
			if (flag[i] == true) {
				System.out.print((i + min)+" ");
			}
		}
	}

}

##2.16

1
给定一个无穷数组A[·]，其中前N个元素都是整数，且已排好序，剩余元素均为∞。n的值未知.给出一个算法，以一个整数x为输入，以O(logn)时间找到数组中的一个位置，并满足其上的元素为x.

###思路：

从a[1]开始，依次访问a[2],a[4],a[8],依次类推，访问至a[$2^i$]，发现a[$2^i$2]为∞，这个花费的时间代价为O(logn)
设k小于i+1, x必定在a[$2^k$]至a[$2^k$2]之间
对这个区间进行二分搜索，定位即可，若搜索到，返回位置，若搜索不到，返回-1.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package homework_chen;

/**
 * 文 件 名 : test216.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.16题目源码
 */

public class test216 {

	/**
	 * @param args
	 * 从a[1]开始，依次访问a[2],a[4],a[8], 依次类推，访问至a[2^i]，发现a[2^(i+1)]为∞，
	 * 这个花费的时间代价为O(logn) 设k小于i+1, x必定在a[2^k]至a[2^(k+1)]之间
	 * 对这个区间进行二分搜索， 定位即可，若搜索到，返回位置，若搜索不到，返回-1.
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] r = { 1, 2, 5, 9, 11, 15, 17, 19, 23, 27, 29, 32, 37, 41, 45, 49,
				54, 57, 59 };
		int x = 60;

		int index = solution(r, x);
		System.out.println("index:" + index);
	}

	/**
	 * @param r 
	 * @param x  
	 * @return index 存在返回下标，不存在返回-1
	 */
	private static int solution(int[] r, int x) {
		int left = 1;
		int right = 1;
		// 定位x的位置
		try {
			while (r[left] < x) {// 当x大于左界值，left翻倍
				left *= 2;
			}// 此时，数组未越界，将其作为右边界
		} catch (ArrayIndexOutOfBoundsException e) {

		} finally {
			right = left;// 此时left已经越界，将其作为右边界
			left = right / 2;
			System.out.println(left + " " + right);
		}
		int index = binSearch(r, left, right, x);
		return index;
	}

	/**
	 * @param r
	 * @param left
	 * @param right
	 * @param x
	 * @return
	 * 二分查找,存在返回index，不存在返回-1
	 */
	private static int binSearch(int[] r, int left, int right, int x) {
		while (left <= right) {
			int mid = (left + right) / 2;
			try {
				if (x < r[mid]) {
					right = mid - 1;
				} else if (x > r[mid]) {
					left = mid + 1;
				} else if (x == r[mid]) {
					return mid;
				}
			} catch (ArrayIndexOutOfBoundsException e) {
				right = mid - 1;
			}
		}
		return -1;
	}
}

##2.23

1
如果一个数组A[1,...,n]中总数超过半数的元素都相同时，该数组被称为含有一个主元素，给定一个数组，设计一个有效算法，确定该数组中是否含有一个主元素，如果有，找出这个元素。需注意的是，该数组的元素之间可能不存在顺序——即不能进行”A[i]<A[j]”的判断，但是可以进行是否相等的判断。

###思路：

1
2
3
4
5
整体采用分治法
当分到只有一个元素时，必定是主元素
对于连续的两段，取得左半边的主元素，取得右半边的主元素
如果左右两边一样，必定为主元素
否则线性扫描，统计次数，找到主元素，若没有返回null

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
60
61
62
63
64
65
66
67
68
69
70
71
72
package homework_chen;

/**
 * 文 件 名 : test223a.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.23题目源码
 */

public class test223a {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] r = { 1, 1, 2, 2, 2, 3, 3, 3 };
		Integer majority = getmajority(r, 0, r.length - 1);
		System.out.println("主元素为:" + majority);

	}

	/**
	 * 求数组的主元素
	 * @param r
	 * @param start
	 * @param end
	 * @return
	 */
	private static Integer getmajority(int[] r, int start, int end) {

		if (start == end) {// 只有一个元素时，必定是主元素
			return r[start];
		}
		int mid = (start + end) / 2;
		Integer majority0 = getmajority(r, start, mid);// 取得左半边的主元素
		Integer majority1 = getmajority(r, mid + 1, end);// 取得右半边的主元素
		if (majority0 == majority1) {// 如果左右两边一样，必定为主元素
			return majority0;
		}
		Integer majority = traverseAndFind(r, majority0, majority1, start, end);// 综合两边主元素判定综合主元素
		return majority;
	}

	/**
	 * 本方法用于返回相邻两段的主元素，若不存在，返回null
	 * @param r
	 * @param majority0
	 * @param majority1
	 * @param start
	 * @param end
	 * @return
	 */
	private static Integer traverseAndFind(int[] r, Integer majority0,
			Integer majority1, int start, int end) {
		int halfRate = (end - start + 1) / 2;//测定程序中的半数
		int fre0 = 0;//统计次数1
		int fre1 = 0;//统计次数2
		for (int i = start; i <= end; i++) {
			if (majority0 != null && r[i] == majority0)
				fre0++;
			if (majority1 != null && r[i] == majority1)
				fre1++;
		}
		if (fre0 > halfRate)//超过半数，满足主元素条件返回
			return majority0;
		if (fre1 > halfRate)
			return majority1;
		return null;//无主元素，返回空指针
	}

}