面试题汇总

1.题目：给定数组A，大小为n,数组元素为0到n-1的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。要求在O(n)的时间复杂度，O(1)的空间复杂度下完成。

  

   解答：这种题目，既然只用这么少的空间，要么从异或角度考虑，相当于只能有一个变量出现。要么充分的利用给定的数组空间。而且时间复杂度为O(n)的话，必然就是遍历那个数组了。

             我们理解一下这个概念：

             假如一个数组中某个数字是 a[i] = t ( 0<=t < n )，那么 如果 a[i] = t + k*n，那么我们是不是需要a[i]%n就可以还原为以前的数组，而且 a[i] / k就可以求出k,是的，我们就利用这种思想来改造之前的数组，然后求出这个k.

             两次遍历数组的方法：考虑A[i]，现在的位置为i,如果采用A来计数，它的位置应该是A[i]%n,找到计数位置，处理这个计数位置的办法就是加n.

             第一次遍历：对A[i]的计算位置加n,加n可以保证A[i]%n的是不变的

             第二次遍历：A数组，最后每一个元素表示为A[i] = x + k * n; 其中x<n,并且k就是我们要统计的频率

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, i;       //n is The length of the Array
    while (scanf("%d", &n) != EOF)
    {   
        int *a = malloc(sizeof(int) * n); 
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);

        for (i = 0; i < n; i++)
            a[a[i] % n] += n;

        for (i = 0; i < n; i++)
        {   
            if (a[i] / n == 0)
                printf("%d does not appear in the array!\n", i); 
            else
                printf("%d appear in the array for %d times\n", i, a[i]/n);
        }   
    }   
}