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

劍指offer之C語言不修改數(shù)組找出重復(fù)的數(shù)字

 更新時間:2019年02月16日 14:13:02   作者:chenyu_insist  
今天小編就為大家分享一篇關(guān)于劍指offer之C語言不修改數(shù)組找出重復(fù)的數(shù)字,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧

1  題目

不修改數(shù)組找出重復(fù)的數(shù)字

在一個長度為N+1的數(shù)組里面的所有數(shù)字都在范圍1~N范圍內(nèi),所以數(shù)組至少有一個數(shù)字是重復(fù)的,請找出重復(fù)數(shù)字,但是不能修改輸入的數(shù)組。

2  思路

思路1:

我們開辟一個新的數(shù)組,初始化為0,然后把原始數(shù)組每個數(shù)據(jù)的值作為下標(biāo),把新數(shù)組通過這個下標(biāo)數(shù)據(jù)取出來,如果取出來是1,就說明這個下標(biāo)數(shù)據(jù)重復(fù)了,如果不是,我們直接放進去,然后進行新數(shù)組值進行++操作。

思路2:

比如數(shù)據(jù)1 2 2 3 4 5 6 7, 我們先找到中間的值(1 + 7) / 2 = 4;然后我們判斷數(shù)組里面每個元素 1到4有多少個,如果有大于4個數(shù)的話,我們一定說明重復(fù)數(shù)據(jù)在范圍1到4里面,反之在范圍4到7中,比如我們上面的數(shù)據(jù)1到4有5個數(shù)據(jù),我們說明可以知道重復(fù)數(shù)據(jù)范圍是1到4,然后我們再把數(shù)據(jù)切一刀,從1到4, 有點像二分法,以此類推,知道我們求出答案。

關(guān)鍵點:

1)我們要個輔助函數(shù):需要知道數(shù)組中從范圍start到end的元素個數(shù)

2)循環(huán)條件是while(end >= start)

3)  退循環(huán)條件是在while里面,if(end == start) {通過輔助函數(shù)得到的個數(shù)大于1就返回這個start值} else {break;}

3  代碼實現(xiàn)

#include <iostream>
using namespace std;
int getCount(const int *a, int len, int start, int end)
{
  if (a == NULL || len <= 0)
  {
    return 0;
  }
  int count = 0;
  for (int i = 0; i < len; ++i)
  {
    if (a[i] >= start && a[i] <= end)
    {
      ++count;
    }
  }
  return count;
}
int getResetNumber(const int *a, int len)
{
  if (a == NULL || len <= 0)
  {
    return -1;
  }
  int start = 1, end = len - 1;
  //int mid = (end - start) / 2 + start;
  while (end >= start)
  {
    int mid = (end - start) / 2 + start;
    int count = getCount(a, len, start, mid);
    if (end == start)
    {
      if (count > 1)
      {
        return start;
      }
      else
      {
        break;
      }
    }
    if (count > (mid - start + 1))
    {
      end = mid;
    }
    else
    {
      start = mid + 1;
    }
  }
  return -1;
}
int main()
{
  std::cout << "請輸入數(shù)組的長度" << std::endl;
  int len = 0;
  std::cin >> len;
  if (len <= 0)
  {
    std::cout << "數(shù)組的長度不合法" << std::endl;
    return -1;
  }
  int *a = new int[len];
  std::cout << "請分別輸入數(shù)組的每個數(shù)據(jù)" << std::endl;
  for (int i = 0; i < len; ++i)
  {
    std::cin >> a[i];
    if (a[i] <= 0 || a[i] >= len)
    {
      std::cout << "輸入的數(shù)據(jù)有誤" << std::endl;
      return -1;
    }
  }
  //int count = getCount(a, len, 1, len - 1);
  int value = getResetNumber(a, len);
  if (value == -1)
  {
    std::cout << "沒有找到重復(fù)的數(shù)據(jù)" << std::endl;
    return -1;
  }
  std::cout << "其中一個重復(fù)的數(shù)據(jù)是" << value << std::endl;
  delete []a;
  return 0;
}

4  運行結(jié)果

請輸入數(shù)組的長度
5
請分別輸入數(shù)組的每個數(shù)據(jù)
1
2
3
4
2
其中一個重復(fù)的數(shù)據(jù)是2

5  本質(zhì)和總結(jié)

在區(qū)間start~end里面,我們要縮小一半?yún)^(qū)間,我們直接找到start~end的中間數(shù)M = (start - end) / 2 + start,然后遍歷數(shù)組,如果在這個范圍的數(shù)據(jù)等于M 大于(M - start + 1)說明這個段區(qū)間有重復(fù)數(shù)據(jù),反之?dāng)?shù)目重復(fù)數(shù)據(jù)在M+1到end區(qū)間,然后每次這切割,以此類推,所以這里要用到循環(huán),用循環(huán)就要條件,我們知道二分法這些操作條件是while(end >= start),既然有循環(huán),那我們必須找到跳出循環(huán)條件的條件在while循環(huán)里面 if (end == start) {輔助函數(shù)個數(shù) > 1} else {break;}

以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

相關(guān)文章

  • C++實現(xiàn)簡易的五子棋游戲

    C++實現(xiàn)簡易的五子棋游戲

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)簡易的五子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • c語言實現(xiàn)詞頻統(tǒng)計的簡單實例

    c語言實現(xiàn)詞頻統(tǒng)計的簡單實例

    下面小編就為大家?guī)硪黄猚語言實現(xiàn)詞頻統(tǒng)計的簡單實例。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-09-09
  • C++中對象的賦值與復(fù)制操作詳細(xì)解析

    C++中對象的賦值與復(fù)制操作詳細(xì)解析

    對象之間的賦值也是通過賦值運算符“=”進行的。本來賦值運算符“=”只能用來對單個的變量賦值,現(xiàn)在被擴展為兩個同類對象之間的賦值,這是通過對賦值運算符的重載實現(xiàn)的
    2013-10-10
  • C語言實現(xiàn)紙牌游戲(小貓釣魚)

    C語言實現(xiàn)紙牌游戲(小貓釣魚)

    這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)紙牌游戲,小貓釣魚游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-10-10
  • OpenCV圖像旋轉(zhuǎn)Rotate的詳細(xì)介紹

    OpenCV圖像旋轉(zhuǎn)Rotate的詳細(xì)介紹

    這篇文章主要介紹了OpenCV圖像旋轉(zhuǎn)Rotate,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-05-05
  • C語言指針筆試題全面解析

    C語言指針筆試題全面解析

    這篇文章主要介紹了C語言指針筆試題全面解析,介紹了其相關(guān)概念,然后分享了幾種用法,具有一定參考價值。需要的朋友可以了解下。
    2021-09-09
  • 詳解Matlab繪制3D玫瑰花的方法(內(nèi)附旋轉(zhuǎn)版本)

    詳解Matlab繪制3D玫瑰花的方法(內(nèi)附旋轉(zhuǎn)版本)

    這篇文章主要為大家介紹了如何利用Matlab繪制3D版的玫瑰花以及旋轉(zhuǎn)版的3D玫瑰花,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以動手試一試
    2022-03-03
  • C++ normal_distribution高斯正態(tài)分布函數(shù)的用法示例

    C++ normal_distribution高斯正態(tài)分布函數(shù)的用法示例

    高斯分布也稱為正態(tài)分布(normal distribution),常用的成熟的生成高斯分布隨機數(shù)序列的方法由Marsaglia和Bray在1964年提出,這篇文章主要給大家介紹了關(guān)于C++ normal_distribution高斯正態(tài)分布函數(shù)用法的相關(guān)資料,需要的朋友可以參考下
    2021-07-07
  • C語言 超詳細(xì)介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表

    C語言 超詳細(xì)介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表

    帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復(fù)雜,一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜,但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢,實現(xiàn)反而簡單
    2022-03-03
  • C++ 在堆上開辟與釋放二維、三維指針詳細(xì)解析

    C++ 在堆上開辟與釋放二維、三維指針詳細(xì)解析

    一維指針其實就相當(dāng)于一維數(shù)組,不用去看書上所說的數(shù)組在內(nèi)存中的首地址這些晦澀的話,以此類推 二維指針就相當(dāng)于二維數(shù)組,新手對一維數(shù)組的開辟與釋放比較容易熟悉
    2013-09-09

最新評論