C語(yǔ)言 數(shù)組中重復(fù)的數(shù)字分析及方法

C語(yǔ)言 數(shù)組中重復(fù)的數(shù)字解決方法：

題目：在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0-n-1的 范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但是不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3.

解法1：對(duì)于數(shù)組進(jìn)行排序，之后對(duì)于已經(jīng)排序的數(shù)組進(jìn)行遍歷便可知道數(shù)組中重復(fù)的數(shù)字。

時(shí)間復(fù)雜度;O(nlogn);

解法2：建立一個(gè)大小為O(N)的哈希表，遍歷數(shù)組中的元素并判斷是否存在于哈希表中。若不存在于哈希表中，將這個(gè)元素加入哈希表之中并且繼續(xù)掃描，若這個(gè)元素存在于哈希表中，則：找到了數(shù)組中重復(fù)的一個(gè)數(shù)字；

時(shí)間復(fù)雜度:O(N),空間復(fù)雜度：O(N)；

解法3：對(duì)于給定的數(shù)組進(jìn)行重排。對(duì)于下標(biāo)為i的元素：如果a[i] == i，掃描下一個(gè)元素；如果不相等將a[i]與a[a[i]]進(jìn)行比較，若是相等則找到了一個(gè)重復(fù)的數(shù)字，若沒(méi)有，那么對(duì)于數(shù)字進(jìn)行交換，依次進(jìn)行。

int DuplicateInArray(int arr[],int size) 
{ 
  int i=0; 
  while(i<size) 
  { 
    if(arr[i] == i) 
      ++i; 
    else 
    { 
      if(arr[i] != arr[arr[i]]) 
      {swap(arr[i],arr[arr[i]]);} 
      else 
      {return arr[i];} 
    } 
  } 
  return -1; 
} 

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！