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