程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C語言 數組中重復的數字分析及方法

C語言 數組中重復的數字分析及方法

編輯:關於C++

C語言 數組中重復的數字分析及方法。本站提示廣大學習愛好者:(C語言 數組中重復的數字分析及方法)文章只能為提供參考,不一定能成為您想要的結果。以下是C語言 數組中重復的數字分析及方法正文


C語言 數組中重復的數字解決方法:

題目:在一個長度為n的數組裡的所有數字都在0-n-1的 范圍內。數組中某些數字是重復的,但是不知道有幾個數字重復了,也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。例如,如果輸入長度為7的數組{2,3,1,0,2,5,3},那麼對應的輸出是重復的數字2或者3.

解法1:對於數組進行排序,之後對於已經排序的數組進行遍歷便可知道數組中重復的數字。

時間復雜度;O(nlogn);

解法2:建立一個大小為O(N)的哈希表,遍歷數組中的元素並判斷是否存在於哈希表中。若不存在於哈希表中,將這個元素加入哈希表之中並且繼續掃描,若這個元素存在於哈希表中,則:找到了數組中重復的一個數字;

時間復雜度:O(N),空間復雜度:O(N);

解法3:對於給定的數組進行重排。對於下標為i的元素:如果a[i] == i,掃描下一個元素;如果不相等將a[i]與a[a[i]]進行比較,若是相等則找到了一個重復的數字,若沒有,那麼對於數字進行交換,依次進行。


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; 
} 

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved