劍指offer--數(shù)組

1.數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半辟拷,請(qǐng)找出這個(gè)數(shù)字村斟。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}徐矩。由于數(shù)字2在數(shù)組中出現(xiàn)了5次,超過(guò)數(shù)組長(zhǎng)度的一半狗热,因此輸出2。如果不存在則輸出0虑省。

/**
 * @ClassName MoreThanHalfNum_Solution
 * @Description 采用陣地攻守的思想:
 *   第一個(gè)數(shù)字作為第一個(gè)士兵匿刮,守陣地;count = 1探颈;
 *   遇到相同元素熟丸,count++;
 *   遇到不相同元素,即為敵人伪节,同歸于盡,count--光羞;當(dāng)遇到count為0的情況绩鸣,又以新的i值作為守陣地的士兵,繼續(xù)下去纱兑,到最后還留在陣地上的士兵呀闻,有可能是主元素。
 *   再加一次循環(huán)潜慎,記錄這個(gè)士兵的個(gè)數(shù)看是否大于數(shù)組一般即可捡多。
 * @Version V1.0
 **/
public class MoreThanHalfNum_Solution {

  public static int MoreThanHalfNum_Solution(int [] array) {
     int cont =0;
     int soldier =array[0];
    for (int i = 0; i < array.length; i++) {
      int value = array[i];
      if (soldier == value) {
        cont++;
      } else {
        cont--;
      }
      if (cont == 0) {
        soldier = value;
        cont++;
      }
    }
    cont=0;
    for(int value : array ){
      if(value==soldier){
        cont++;
      }
    }

     return cont>array.length/2 ? soldier:0;
  }

  public static void main(String[] args) {
    int[] array =  {1,2,3,2,2,2,5,4,2};
    MoreThanHalfNum_Solution(array);
  }

}

2.在一個(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ù)字驳遵。

/**
 * @ClassName numberRepeat
 * @Description
 * @Version V1.0
 **/
public class NumberRepeat {
  // Parameters:
  //    numbers:     an array of integers
  //    length:      the length of array numbers
  //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
  //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
  //    這里要特別注意~返回任意重復(fù)的一個(gè)淫奔,賦值duplication[0]
  // Return value:       true if the input is valid, and there are some duplications in the array number
  //                     otherwise false
  public boolean duplicate(int numbers[],int length,int [] duplication) {

     for(int i=0;i<length;i++){
       while (numbers[i]!=i){
         if(numbers[i] == numbers[numbers[i]]){
            duplication[0] =  numbers[i];
            return true;
         }
         swap(numbers,i,numbers[i]);
       }

     }

     return false;
  }

  private void swap(int[] numbers, int i, int j) {
    int t =numbers[i];
    numbers[i] = numbers[j];
    numbers[j]=t;
  }

}

3.給定一個(gè)二維數(shù)組,其每一行從左到右遞增排序堤结,從上到下也是遞增排序唆迁。給定一個(gè)數(shù),判斷這個(gè)數(shù)是否在該二維數(shù)組中竞穷。


/**
 * @ClassName find
 * @Description
 * @Version V1.0
 **/
public class find {

  public boolean find(int target, int [][] array) {
    if(array==null || array.length==0 || array[0].length==0){
      return false;
    }
     //行數(shù)
    int rows = array.length;
     //列數(shù)
    int cols = array[0].length;
    //右上角
    int r=0,c=cols-1;
    while (r<rows-1 && c>0){
      if(target>array[r][c]){
        r++;
      }else {
        c--;
      }
      if(target==array[r][c]){
        return true;
      }
    }
     return false;
  }
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末唐责,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子瘾带,更是在濱河造成了極大的恐慌鼠哥,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件看政,死亡現(xiàn)場(chǎng)離奇詭異朴恳,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)允蚣,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén)于颖,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人嚷兔,你說(shuō)我怎么就攤上這事森渐。” “怎么了冒晰?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵同衣,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我壶运,道長(zhǎng)耐齐,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮蚪缀,結(jié)果婚禮上秫逝,老公的妹妹穿的比我還像新娘。我一直安慰自己询枚,他們只是感情好违帆,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著金蜀,像睡著了一般刷后。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上渊抄,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天尝胆,我揣著相機(jī)與錄音,去河邊找鬼护桦。 笑死含衔,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的二庵。 我是一名探鬼主播贪染,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼催享!你這毒婦竟也來(lái)了杭隙?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤因妙,失蹤者是張志新(化名)和其女友劉穎痰憎,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體攀涵,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡铣耘,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了汁果。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片涡拘。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡玲躯,死狀恐怖据德,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情跷车,我是刑警寧澤棘利,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站朽缴,受9級(jí)特大地震影響善玫,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜密强,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一茅郎、第九天 我趴在偏房一處隱蔽的房頂上張望蜗元。 院中可真熱鬧,春花似錦系冗、人聲如沸奕扣。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)惯豆。三九已至,卻和暖如春奔害,著一層夾襖步出監(jiān)牢的瞬間楷兽,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工华临, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留芯杀,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓雅潭,卻偏偏與公主長(zhǎng)得像瘪匿,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子寻馏,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 數(shù)組 記錄《劍指offer》中所有關(guān)于數(shù)組的題目棋弥,以及LeetCode中的相似題目 相關(guān)題目列表 說(shuō)明 由于簡(jiǎn)書(shū)...
    wenmingxing閱讀 1,522評(píng)論 1 12
  • 下面代碼的輸出是什么 因?yàn)閟izeof(data1)是求數(shù)組的大小顽染,每個(gè)整數(shù)占4個(gè)字節(jié);第二個(gè)是因?yàn)橹羔樥?個(gè)字節(jié)...
    世界上的一道風(fēng)閱讀 346評(píng)論 0 0
  • 找出數(shù)組中重復(fù)的數(shù)字 在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0~n-1的范圍內(nèi)轰绵。數(shù)組中某些數(shù)字是重復(fù)的粉寞,但不知道有幾...
    Longshihua閱讀 599評(píng)論 0 3
  • 1.二維數(shù)組的查找 在一個(gè)二維數(shù)組中(每個(gè)一維數(shù)組的長(zhǎng)度相同),每一行都按照從左到右遞增的順序排序左腔,每一列都按照從...
    linjiason閱讀 733評(píng)論 0 0
  • 說(shuō)明: 本文中出現(xiàn)的所有算法題皆來(lái)自胚罂眩客網(wǎng)-劍指Offer在線編程題,在此只是作為轉(zhuǎn)載和記錄液样,用于本人學(xué)習(xí)使用振亮,不...
    秋意思寒閱讀 1,158評(píng)論 1 1