快捷導(dǎo)航

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

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

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

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ù)字，若沒有，那么對(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ì)本站的支持！

您可能感興趣的文章:

相關(guān)文章

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