1.數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(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次，超過數(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;
  }
}