欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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ù)組進行排序,之后對于已經(jīng)排序的數(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++中的std::async()詳解

    C++中的std::async()詳解

    這篇文章主要給大家介紹了關于C++中std::async()的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-11-11
  • C++ CopyFile,MoveFile用法案例詳解

    C++ CopyFile,MoveFile用法案例詳解

    這篇文章主要介紹了C++ CopyFile,MoveFile用法案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-09-09
  • C++中inline用法案例詳解

    C++中inline用法案例詳解

    這篇文章主要介紹了C++中inline用法案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-09-09
  • C++指向函數(shù)的指針用法詳解

    C++指向函數(shù)的指針用法詳解

    這篇文章主要介紹了C++指向函數(shù)的指針用法,對函數(shù)指針的聲明、優(yōu)先級、指針類型等概念做了較為詳盡的分析,需要的朋友可以參考下
    2014-09-09
  • C++函數(shù)重載的深入解析

    C++函數(shù)重載的深入解析

    在C++中,我們也能夠把具有相同功能的函數(shù)整合到一個函數(shù)上,而不必去寫好多個函數(shù)名不同的函數(shù),這叫做函數(shù)的重載。以下是對C++中的函數(shù)重載進行了詳細的分析介紹,需要的朋友可以過來參考下
    2013-07-07
  • C++ string.erase()用法詳解

    C++ string.erase()用法詳解

    這篇文章主要介紹了C++ string.erase()用法詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-09-09
  • c語言求1+2+...+n的解決方法

    c語言求1+2+...+n的解決方法

    本篇文章是對在c語言中求1+2+...+n的解決方法進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • C++新特性詳細分析基于范圍的for循環(huán)

    C++新特性詳細分析基于范圍的for循環(huán)

    C++11這次的更新帶來了令很多C++程序員期待已久的for?range循環(huán),每次看到javascript,?lua里的for?range,心想要是C++能有多好,心里別提多酸了。這次C++11不負眾望,再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法
    2022-04-04
  • pybind11: C++ 工程提供 Python 接口的實例代碼

    pybind11: C++ 工程提供 Python 接口的實例代碼

    這篇文章主要介紹了pybind11: C++ 工程如何提供 Python 接口,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-09-09
  • C++基礎入門之運算符

    C++基礎入門之運算符

    下面小編就為大家?guī)硪黄P于C++運算符基礎的文章。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-11-11

最新評論