xiaobaoqiu Blog

Think More, Code Less

数据结构与算法分析第二章

<<数据结构与算法分析-C语言描述>>

1.最大子序列和

O(n3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
* 时间复杂度O(n^3)
*/
int Chapter2::maxSubSeqSum1(const int A[], int N)
{
    int maxSum = 0;
    for(int i=0; i<N; i++)
        for(int j=i; j<N; j++)
        {
            int thisSum = 0;
            for(int k=i; k<=j; k++)
                thisSum += A[k];
            if(thisSum > maxSum) maxSum = thisSum;
        }

        return maxSum;
}

O(n2)

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

/**
*   算法1的最里层循环不是必须的
*   时间复杂度:O(n^2)
*/
int Chapter2::maxSubSeqSum2(const int A[], int N)
{
        int maxSum = 0;
        for(int i=0; i<N; i++)
        {
                int thisSum = 0;
                for(int j=i; j<N; j++)
                {
                        thisSum +=A[j];
                        if(thisSum > maxSum)    maxSum = thisSum;
                }
        }

        return maxSum;
}

分治,O(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

/**
* 分治,划分为作用两个字数组
* A[l,...,M], A[M+1,...,R]
* 则最大子序列和来自三部分:左侧的最大子序列和,右侧的最大子序列和,跨越A[M]和A[M+1]的最大子序列号
* 1,2情况递归可以完成,情况三其实就是求最测以A[M]结尾的最大和,右侧就是以A[M+1]开头的最大和
*
* 时间复杂度:T(n) = 2T(n/2) + O(n)
* 即 O(nlogn)
*/
int Chapter2::maxSubSeqSum3(const int A[], int L, int R)
{
        if(L == R) return A[L] < 0 ?0 : A[L];
        int M = (L + R) >> 1;
        int maxSumL = maxSubSeqSum3(A, L, M);
        int maxSumR = maxSubSeqSum3(A, M+1, R);
        int maxL = 0, sumL = 0;
        for(int i = M; i>=L; i--)
        {
                sumL += A[i];
                if(sumL > maxL) maxL = sumL;
        }
        int maxR = 0, sumR = 0;
        for(int i = M+1; i<=R; i++)
        {
                sumR += A[i];
                if(sumR > maxR) maxR = sumR;
        }

        return max(max(maxSumL, maxSumR), maxL+maxR);
}

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**
* 时间复杂度 O(n)
*/
int Chapter2::maxSubSeqSum4(const int A[], int N)
{
        int maxSum = 0, thisSum = 0;
        for(int i=0; i<N; i++)
        {
                thisSum += A[i];
                if(thisSum > maxSum) maxSum = thisSum;
                else if(thisSum < 0) thisSum = 0;
        }

        return maxSum;
}

2.gcd

1
2
3
4
5
6
7
8
9
10
11

unsigned int Chapter2::gcd(unsigned int L, unsigned int R)
{
        unsigned rem;
        while(R > 0)
        {
                rem = L % R;
                L = R;
                R = rem;
        }
        return L;
}

3.快速幂

递归

1
2
3
4
5
6
7

long Chapter2::pow1(long x, unsigned n)
{
        if(n == 0) return 1;
        if(n == 1) return x;
        if(isEven((n))) return pow(x*x, n>>1);
        else return pow(x*x, n>>1) * x;
}

非递归

1
2
3
4
5
6
7
8
9
10

long Chapter2::pow2(long x, unsigned n)
{
        long base = x, ret = 1L;
        while(n > 0)
        {
                if(isEven(n)) {base *= base; n>>=1;}
                else {ret *= base; n-=1;}
        }
        return ret;
}

4.随机置换

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
* 生成前N个数的随机置换
* 如 N = 3, 生成 [2 1 3]
*/
void Chapter2::randomSeq(int* A, int N)
{
        for(int i=0; i<N; i++)
                A[i] = i+1;
        for(int i=1; i<N; i++)
        {
                swap(A[i], A[random(N)]);
        }
}

5.出现次数超过一半的数

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

/**
* 寻找数组的主要元素:即一个N个元素的数组中,某一个元素出现次数 >= N/2次
* 如 [6, 8, 8, 2, 3, 4, 8, 8, 8]中8是主要元素
* 思路:比较A1和A2,相等则将A1放入一个新的数组B,不想等则放弃;同样比较A3,A4...
* 递归处理数组B
*
* 注意这里只是返回了一个候选解,如果存在,则一定是这个元素
* 不存在的情况需要再扫描一遍数组
*/
 int Chapter2::mainElement(const int* A, int N)
 {
    int Candidata, nTimes = 0, i=0;
    while(i < N)
    {
        if(nTimes==0) { Candidata = A[i]; nTimes = 1; }
        else
        {
            if(A[i] != Candidata) --nTimes;
            else ++nTimes;
        }
        ++i;
    }
    return Candidata;
}