一个数组a[10] {1,2,3,4,4,5,6,7,8,9}
怎么找出那个相同的数字?

三种方法

1、先排序再两两比较
2、嵌套for循环
3、把2用指针做一遍

你贴下代码好吗。谢谢

引用:

以下是引用 hjh10845 在 2008-5-1 23:24 的发言：

你贴下代码好吗。谢谢

我可不愿意这样剥夺你思考的权利，你先自己试着写写

你把关键的指导下好吗 谢谢

复制内容到剪贴板

代码:

/*************************************************
          以上略
*************************************************/
        for(i=0;i<10;++i)
                for(j=0;j<10;++j)
                        if(a[i]==a[j])
                        {
                                b[k]=a[i];
                                ++k;
                                n++;
                         }
                           ………
/**************************************************
                以下略
**************************************************/

假如是n个数的范围为1 ~ n-1，当中有一对相同，那么：
O(n)两种  O(nlogn)两种或以上  O(n^2)三种以上

至少7种方法

再假如，你数组中的数已经有序，那么还可以有一种O(logn)

再或者，这n个数无序并且大小不定，但必有且只有一对相同，
那么最好的时间复杂度是O(nlogn)



[ 本帖最后由 雨中飛燕 于 2008-5-2 03:28 编辑 ]

建二叉树，因为二叉树节点插入时要求输入的权值唯一，这里数组中每一个元素可以作为二叉树的权值进行构建二叉树，若某个权值插入失败，则说明二叉树中已经拥有这个权值，则认定该数是重复的，输出，反复的进行二叉树插入操作，直到数组中所有元素全部消耗为止。

给LZ小写一段
#include <assert.h>
#include <stdio.h>

#define STACK_SIZE    100

typedef struct tagBiTreeNode
{
    int nKey;
    struct tagBiTreeNode *pLChild, *pRChild;
    struct tagBiTreeNode *pParent;
} BI_TREE_NODE, *PBI_TREE_NODE;

int insert(const int& nKey, const PBI_TREE_NODE _pNode)
{
    assert(_pNode);
    PBI_TREE_NODE pNode = (PBI_TREE_NODE)_pNode;
    int nFlag = 1, nRet = 0;
    while(nFlag)
    {
        if(nKey > pNode->nKey)
        {
            if(pNode->pRChild)
                pNode = pNode->pRChild;
            else
            {
                pNode->pRChild = new BI_TREE_NODE;
                assert(pNode->pRChild);
                pNode->pRChild->pParent = pNode;
                pNode = pNode->pRChild;
                pNode->nKey = nKey;
                pNode->pLChild = NULL;
                pNode->pRChild = NULL;
                nFlag = 0;    
            }
        }
        else if(nKey < pNode->nKey)
        {
            if(pNode->pLChild)
                pNode = pNode->pLChild;
            else
            {
                pNode->pLChild = new BI_TREE_NODE;
                assert(pNode->pLChild);
                pNode->pLChild->pParent = pNode;
                pNode = pNode->pLChild;
                pNode->nKey = nKey;
                pNode->pLChild = NULL;
                pNode->pRChild = NULL;
                nFlag = 0;
            }
        }
        else
        {
            nFlag = 0;
            nRet = 1;
        }
    }
    return nRet;
}

void dispose(PBI_TREE_NODE pRoot)
{
    PBI_TREE_NODE pStack[STACK_SIZE];
    int nTop = -1;
    
    pStack[++nTop] = pRoot;
    while(nTop >= 0)
    {
        PBI_TREE_NODE pNode = pStack[nTop--];
        if(pNode)
        {
            pStack[++nTop] = pNode->pLChild;
            pStack[++nTop] = pNode->pRChild;
        }
        delete pNode;
    }
}

void preorder(PBI_TREE_NODE pNode)
{
    if(pNode)
    {
        printf("%3d", pNode->nKey);
        preorder(pNode->pLChild);
        preorder(pNode->pRChild);
    }
}

int main(int argc, char* argv[])
{
    int arrKey[10] = {1,2,3,4,4,5,6,7,8,9};
    PBI_TREE_NODE pRoot = new BI_TREE_NODE;
    assert(pRoot);
    // insert the first node
    pRoot->nKey = arrKey[0];
    pRoot->pLChild = NULL;
    pRoot->pRChild = NULL;
    pRoot->pParent = NULL;
    for(int i = 1; i < 10; i++)
    {
        if(insert(arrKey[i], pRoot))
        {
            printf("The key = %d is already exist!\n", arrKey[i]);
        }
    }
    
    // sorted result
    preorder(pRoot);
    printf("\n");

    // dispose
    dispose(pRoot);
    pRoot = NULL;

    return 0;
}

根据燕子的思路写的， 能力有限，实在写不出O(lgn)的算法。。燕子可否提示一下?
下面是代码:(C++版)

复制内容到剪贴板

代码:

//***********数组无序的情况**********
int ElementUniqueness(int* arr,int size_)
{ //时间复杂度 O(n^2)
    for(int i=0;i<size_;++i)
      for(int j=i+1;j<size_;++j)
          if(arr[i]==arr[j]) return arr[i];
    return -10000;
}
int ElementUniqueness(int* arr,int size_)
{ //时间复杂度 O(n^2)
    for(int *i=arr;i<arr+size_;++i)
      for(int *j=i+1;j<arr+size_;++j)
          if(*i == *j) return *i;
    return -10000;
}
int ElementUniqueness(int* arr,int size_)
{ //时间复杂度 O(n^2)
    if(size_>1)
    {
      ElementUniqueness(arr,size_-1);
      int key = arr[size_-1];
      for(int i=0;i<size_-1;++i)
        if(key==arr[i]) return arr[i];
      return -10000;
    }    
}
//上面是一般的O(n^2)算法，下面用预排序来实现O(n^2)
//排序为O(n^2)的可用：选择，插入，冒泡等，这里用插入
void InsertSort(int* arr,int size_)
{
    for(int i=1;i<size_;++i)
    {
       int key=arr[i];
       int j=i-1;
       for(;j>=0&&key<arr[j];--j)
           arr[j+1]=arr[j];
       arr[j+1]=key;
    }
}
int ElementUniqueness(int* arr,int size_)
{
    InsertSort(arr,size_);
    for(int i=0;i<size_-1;++i)
      if(arr[i]==arr[i+1]) return arr[i];
    return -10000;
}
//时间复杂度在O(n)的
int ElementUniqueness(int *arr,int size_,int max_n)
{
    int *count=new int[max_n+1];
    for(int i=0;i<=max_n;++i) count[i]=0;
    for(int j=0;j<size_;++j) count[arr[j]] +=1;
    for(int k=0;k<size_;++k)
        if(count[arr[k]]>1) { delete [] count; return arr[k];}
    delete [] count;
    return -10000;
}
//下面时间复杂度为O(n)的可选用计数排序来做预排序
void countSort(int* arr,int size_,int max_n)
{
    int *count=new int[max_n+1];
    int *temp =new int[size_];
    for(int i=0;i<=max_n;++i) count[i]=0;
    for(int j=0;j<size_;++j) temp[j]=arr[j];

    for(int m=0;m<size_;++m) count[arr[m]] +=1;
    for(int n=1;n<size_;++n) count[n] +=count[n-1];
    
    for(int k=0;k<size_;++k)
    {
        arr[count[temp[k]]-1] = temp[k];
        count[temp[k]] -=1;
    }
    delete [] count; delete [] temp;
}
int ElementUniqueness(int* arr,int size_,int max_n)
{
    countSort(arr,size_,max_n);
    for(int i=0;i<size_-1;++i)
      if(arr[i]==arr[i+1]) return arr[i];
    return -10000;
}
//时间复杂度为O(nlgn)的可选合并，快速，堆等排序做预排序，下面用快速给出
void swap(int* arr,int i,int j)
{
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}
int partition(int* arr,int l,int r)
{
    int key = arr[l];
    int i=l,j=r;
    for(++i;i<j;)
    {
        for(;arr[i]<key;++i);
        for(;arr[j]>key;--j);
        swap(arr,i,j);
    }
    swap(arr,i,j);
    swap(arr,l,j);
    return j;
}
void Qsort(int* arr,int l,int r)
{
    if(l<r)
    {
        int j=partition(arr,l,r);
        Qsort(arr,l,j-1);
        Qsort(arr,j+1,r);
    }
}
int ElementUniqueness(int* arr,int size_)
{
   Qsort(arr,0,size_-1);
   for(int i=0;i<size_-1;++i)
       if(arr[i]==arr[i+1]) return arr[i];
    return -10000;
}