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;
}
}
