经典算法题

共500字 阅读时长约2分 访问量次

天勤算法题积累

寻找主元素

线性表真题 3：一个数组有 N 个元素，其中有超过 N/2 的元素相同，请找出这个元素。时间复杂度为 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
/**
 *
 * 如果一个数组中存在一个主元素（个数大于n/2），如果两个不相等的元素两两抵消，那么最终一定剩下的是主元素。
 *
 */

int major_element(int A[], int n)
{
	/* non-negative returned if major element exist. */
	int seed = A[0];
	int cnt = 1;
	int p;
	for (int i = 1; i < n; i++) {
		if(seed == A[i])
			cnt++;
		else
			if(cnt>0) cnt--;
			else seed = A[i];
	}
	cnt = 0;
	for(int i = 0; i < n; i++)
		if(A[i] == seed) cnt++;
	if(cnt > (n>>1))
		return p;
	return -1;
}

求 N 个字符的全排列

栈与队列思考题 2：对 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
/**
 *
 *设str是含有n个不同字符的数组例如12345，perm（str,k,n）为str[0]~str[k]的所有字符全排序输出函数，
 *n为str数组字符个数。以此类推，perm(str,k-1,n)处理的字符个数比perm(str,k,n)处理的字符个数少一个。
 *假定perm(str,k-1,n)可求，对于第k个位置可以任取str[0]~str[k-1]内任意元素作为str[k]，
 *再组合perm(str,k+1,n)得到perm(str,k,n)。再递归之前先选取一个元素和位置k的元素交换，这一级递归完成之后，
 *再把元素交换回来，保证初始元素顺序不改变，以实现所有字符都能在位置k上完成一次递归。
 *
 */
void perm(int str[], int k, int n) {
    int i, j;
    int temp;
    if (k == 0) {
        for (i = 0; i < n; i++) cout << str[i];
        cout << endl;
    } else {
        for (i = 0; i <= k; i++) {
            temp = str[k];
            str[k] = str[i];
            str[i] = temp; //任取str[i]与str[k]交换
            perm(str, k-1, n);
            temp = str[k];
            str[k] = str[i];
            str[i] = temp; //还原str[k]和str[i]得到原始数组，下次再任取
        }
    }
}