二、编程题
1、数组乘积(15分)
输入：一个长度为n的整数数组input
输出：一个长度为n的整数数组result，满足result[i] = input数组中除了input[i]之外所有数的乘积(假设不会溢出)。比如输入：input = {2,3,4,5}，输出result = {60,40,30,24}
程序时间和空间复杂度越小越好。
C/C++：
int *cal(int* input , int n);
Java:
int[] cal(int[] input);
[cpp] view plaincopy
int *cal(int* input , int n)
{
int i ;
int *result = new int[n];
result[0] = 1;
for(i = 1 ; i < n ; ++i)
result[i] = result[i-1]*input[i-1];
result[0] = input[n-1];
for(i = n-2 ; i > 0 ; --i)
{
result[i] *= result[0];
result[0] *= input[i];
}
return result;
}
2、异形数(25分)
在一个长度为n的整形数组a里，除了三个数字只出现一次外，其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。
例如： a = {1,3,7,9,5,9,4,3,6,1,7}，输出4或5或6
C/C++：
void find(int* a , int n);
Java:
void find(int[] a);
[cpp] view plaincopy
// lowbit表示的是某个数从右往左扫描第一次出现1的位置
int lowbit(int x)
{
return x&~(x-1);
}
void find(int* a , int n)
{
int i , xors;
xors = 0;
for(i = 0 ; i < n ; ++i)
xors ^= a[i];
// 三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组
int fips = 0;
for(i = 0 ; i < n ; ++i)
fips ^= lowbit(xors ^ a[i]);
// 表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
int b; // 假设三个只出现一次的其中一个数为b
b = 0;
for(i = 0 ; i < n ; ++i)
{
if(lowbit(xors ^ a[i]) == fips)
b ^= a[i];
}
// 成功找到三个数中一个数
cout<
}
3、朋友圈(25分)
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...)，则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
C/C++：
int friends(int n , int m , int* r[]);
Java:
int friends(int n , int m , int[][] r);
[cpp] view plaincopy
// 简单的并查集应用
int set[10001];
inline int find(int x) //带路径优化的并查集查找算法
{
int i , j , r;
r = x;
while(set[r] != r)
r = set[r];
i = x;
while(i != r)
{
j = set[i];
set[i] = r;
i = j;
}
return r;
}
inline void merge(int x , int y) //优化的并查集归并算法
{
int t = find(x);
int h = find(y);
if(t < h)
set[h] = t;
else
set[t] = h;
}
int friends(int n , int m , int* r[])
{
int i , count;
for(i = 1 ; i <= n ; ++i) //初始化并查集，各点为孤立点，分支数为n
set[i] = i;
for(i = 0 ; i < m ; ++i)
merge(r[i][0] , r[i][1]);
count = 0;
for(i = 1 ; i <= n ; ++i)
{
if(set[i] == i)
++count;
}
return count;
}
