剑指offer--数组

1.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

/**
 * @ClassName MoreThanHalfNum_Solution
 * @Description 采用阵地攻守的思想：
 *   第一个数字作为第一个士兵，守阵地；count = 1；
 *   遇到相同元素，count++;
 *   遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
 *   再加一次循环，记录这个士兵的个数看是否大于数组一般即可。
 * @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.在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

/**
 * @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++
  //    这里要特别注意~返回任意重复的一个，赋值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.给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

/**
 * @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;
    }
     //行数
    int rows = array.length;
     //列数
    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;
  }
}