2.15 本章习题

本章数组和队列的习题

1、不用除法运算

两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]_a[1]_a[2]...*a[N-1]/a[i]；要求：

1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O(n)，空间复杂度O(1)。

提示：题目要求b[i] = a[0]_a[1]_a[2]..._a[N-1]/a[i] ，相当于求：a[0]_a[1]_a[2]_a[3]...a[i-1]_a[i+1].._a[N-1]，等价于除掉当前元素a[i]，其他所有元素(a[i]左边部分，和a[i]右边部分)的积。

记left[i]=∏a[k], (k=1...i-1); right=∏a[k], (k=i+1...n)，根据题目描述b[i]=left[i] * right[i]，对于每一个b[i]初始化为1，left[i]和right[i]两部分可以分开两次相乘，即对于循环变量i=1...n, b[i]=left[i];b[n-i]=right[n-i]，循环完成时即可完成计算。

参考代码如下所示：

void Multiplication(int a[], int output[], int length)
{
    int left = 1;
    int right = 1;
    for (int i = 0; i < length; i++)
        output[i] = 1;
    for (int i = 0; i < length; i++)
    {
        output[i] *= left;
        output[length - i - 1] *= right;
        left *= a[i];
        right *= a[length - i - 1];
    }
}

3、找出数组中唯一的重复元素

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

4、找出唯一出现的数

一个数组里，数都是两两出现的，但是有三个数是唯一出现的，找出这三个数。

5、找出反序的个数

给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。即：数组a[]; 对于i a[j],则称这是一个反序。给定一个数组，要求写一个函数，计算出这个数组里所有反序的个数。

6、

有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1