小米2019校園招聘筆試題和面試題答案(二)

二、編程題

　　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]);

　　count = 0;

　　for(i = 1 ; i <= n ; ++i)

　　{

　　if(set[i] == i)

　　++count;

　　}

　　return count;

　　}