白话经典算法系列之十一道有趣的GOOGLE面试题

2012-11-28 16:07| 发布者: 红黑魂| 查看: 4396| 评论: 0|来自: CSDN博客

摘要: 最近在微博上看到一道有趣的GOOGLE面试题，见下图：文字版：一个大小为n的数组，里面的数都属于范围，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。这个题目要求用O(n)的时间复杂度，这意味 ...

有了上面的分析，代码不难写出：

[cpp]view plaincopy
//GOOGLE面试题  
//一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。  
//By MoreWindows (http://blog.csdn.net/MoreWindows)  
#include <stdio.h>  
const int NO_REPEAT_FLAG = -1;  
void Swap(int &x, int &y)  
{  
    int t = x;  
    x = y;  
    y = t;  
}  
//类似于基数排序，找出数组中第一个重复元素。  
int RadixSort(int a[], int n)  
{  
    int i;  
    for (i = 0; i < n; i++)  
    {  
        while (i != a[i])  
        {  
            if (a[i] == a[a[i]])  
                return a[i];  
            Swap(a[i], a[a[i]]);  
        }  
    }  
    return NO_REPEAT_FLAG;  
}  
void PrintfArray(int a[], int n)  
{  
    for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);  
    putchar('\n');  
}  
int main()  
{  
    printf("    白话经典算法系列之十 一道有趣的GOOGLE面试题 \n");        
    printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   
  
    const int MAXN = 10;  
    int a[MAXN] = {2, 4, 1, 5, 7,  6, 1, 9, 0, 2};  
    //int a[MAXN] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  
  
    printf("数组为: \n");  
    PrintfArray(a, MAXN);  
  
    int nRepeatNumber = RadixSort(a, MAXN);  
    if (nRepeatNumber != NO_REPEAT_FLAG)  
        printf("该数组有重复元素，此元素为%d\n", nRepeatNumber);  
    else  
        printf("该数组没有重复元素\n");  
    return 0;  
}  