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

更新時間：2017年03月19日 09:52:45 投稿：lqh

這篇文章主要介紹了C語言數(shù)組中重復的數(shù)字分析及方法的相關資料,需要的朋友可以參考下

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

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

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

時間復雜度;O(nlogn);

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

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

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

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

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

您可能感興趣的文章:

C/C++中memset,memcpy的使用及fill對數(shù)組的操作
這篇文章主要介紹了C/C++中memset,memcpy的使用及fill對數(shù)組的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
C/C++中的OpenCV讀取視頻與調用攝像頭
這篇文章主要介紹了C/C++中的OpenCV讀取視頻與調用攝像頭，具有很好的參考價值，希望對大家有所幫助。
2022-11-11
基于C語言實現(xiàn)學生成績管理系統(tǒng)
這篇文章主要介紹了基于C語言實現(xiàn)學生成績管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-01-01
基于Matlab實現(xiàn)繪制3D足球的示例代碼
這篇文章主要為大家詳細介紹了如何利用Matlab實現(xiàn)繪制3D足球，文中的示例代碼講解詳細，對我們學習Matlab有一定幫助，需要的可以參考一下
2022-11-11
基于C++自動化編譯工具的使用詳解
本篇文章是對C++中自動化編譯工具的使用進行了詳細的分析介紹，需要的朋友參考下
2013-05-05
C語言中getch()函數(shù)詳解及簡單實例
這篇文章主要介紹了C語言中getch()函數(shù)詳解及簡單實例的相關資料,需要的朋友可以參考下
2017-03-03
C語言實現(xiàn)JSON解析器的方法步驟
JSON是一種非常流行的數(shù)據(jù)格式,本文主要介紹了C語言實現(xiàn)JSON解析器的方法步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
2024-08-08
C++?opencv學習之圖像像素的邏輯操作
圖像的像素操作包括讀寫操作、算數(shù)操作、邏輯運算操作等,下面這篇文章主要給大家介紹了關于C++?opencv學習之圖像像素的邏輯操作的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
2022-11-11
詳解C++語言中std::array的神奇用法
本文的代碼都在C++17環(huán)境下編譯運行。當前主流的g++版本已經能支持C++17標準，但是很多版本（如gcc 7.3）的C++17特性不是默認打開的，需要手工添加編譯選項-std=c++17，具體內容詳情跟隨小編一起學習吧
2021-05-05
如何利用C語言輸出3D立體感心形圖詳解
其實我們在程序中也有很多樂趣的,只是很多人不善于發(fā)現(xiàn),這篇文章主要給大家介紹了關于C語言輸出3D立體感心形圖的相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下
2021-12-12