C語言 數(shù)組中重復(fù)的數(shù)字分析及方法
更新時間：2017年03月19日 09:52:45 投稿：lqh
這篇文章主要介紹了C語言 數(shù)組中重復(fù)的數(shù)字分析及方法的相關(guān)資料,需要的朋友可以參考下
C語言 數(shù)組中重復(fù)的數(shù)字解決方法：
題目：在一個長度為n的數(shù)組里的所有數(shù)字都在0-n-1的 范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但是不知道有幾個數(shù)字重復(fù)了，也不知道每個數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3.
解法1：對于數(shù)組進(jìn)行排序，之后對于已經(jīng)排序的數(shù)組進(jìn)行遍歷便可知道數(shù)組中重復(fù)的數(shù)字。
時間復(fù)雜度;O(nlogn);
解法2：建立一個大小為O(N)的哈希表，遍歷數(shù)組中的元素并判斷是否存在于哈希表中。若不存在于哈希表中，將這個元素加入哈希表之中并且繼續(xù)掃描，若這個元素存在于哈希表中，則：找到了數(shù)組中重復(fù)的一個數(shù)字；
時間復(fù)雜度:O(N),空間復(fù)雜度：O(N)；
解法3：對于給定的數(shù)組進(jìn)行重排。對于下標(biāo)為i的元素：如果a[i] == i，掃描下一個元素；如果不相等將a[i]與a[a[i]]進(jìn)行比較，若是相等則找到了一個重復(fù)的數(shù)字，若沒有，那么對于數(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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C++中std::async()的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了C++ CopyFile,MoveFile用法案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++中inline用法案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++指向函數(shù)的指針用法,對函數(shù)指針的聲明、優(yōu)先級、指針類型等概念做了較為詳盡的分析,需要的朋友可以參考下2014-09-09
在C++中，我們也能夠把具有相同功能的函數(shù)整合到一個函數(shù)上，而不必去寫好多個函數(shù)名不同的函數(shù)，這叫做函數(shù)的重載。以下是對C++中的函數(shù)重載進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-07-07
這篇文章主要介紹了C++ string.erase()用法詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
本篇文章是對在c語言中求1+2+...+n的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++新特性詳細(xì)分析基于范圍的for循環(huán)
C++11這次的更新帶來了令很多C++程序員期待已久的for?range循環(huán)，每次看到j(luò)avascript，?lua里的for?range，心想要是C++能有多好，心里別提多酸了。這次C++11不負(fù)眾望，再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法2022-04-04
pybind11: C++ 工程提供 Python 接口的實例代碼
這篇文章主要介紹了pybind11: C++ 工程如何提供 Python 接口,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
下面小編就為大家?guī)硪黄P(guān)于C++運(yùn)算符基礎(chǔ)的文章。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-11-11