数组中超过一半的数字 2.3

两种方法，一个是基于快排的partition函数，但这种存在一个问题，如果数组{1,1,1,1,1,1,2,3,4,5,6}，这样的话，partition返回的数字为2所对应的index

? ?

所以这种方法需要添加一个判定数组中是否存在超过一半数字的数

? ?

另外一种是，首先认为第一个数就是我们想找的，设置一个time，初始为1，然后遍历后面的数，如果与这个数相同，那么time++，不同则time--，time减到0时，将这个数换成当前数，并将time置为1，再往后遍历

? ?

同样应该判定输入数组是否符合要求

? ?

package moreThanHalfNum29;

? ?

public class MoreThanHalfNum29 {

static int moreThanHalfNum(int[] a, int length) {

if (length == 0) {

return 0;

}

int mid = length >> 1;

int start = 0;

int end = length - 1;

int index = partition(a, start, end);

while (index != mid) {

if (index > mid) {

end = index - 1;

index = partition(a, start, end);

} else {

start = index + 1;

index = partition(a, start, end);

}

}

int result = a[mid];

return result;

? ?

}

? ?

static int partition(int[] a, int left, int right) {

int i, j, t, key;

if (left >= right)

return 0;

? ?

key = a[left];

i = left;

j = right;

while (i != j) {

while (a[j] >= key && i < j)

j--;

while (a[i] <= key && i < j)

i++;

if (i < j) {

t = a[i];

a[i] = a[j];

a[j] = t;

}

}

a[left] = a[i];

a[i] = key;

return i;

}

? ?

static int sol2(int[] a) {

if (checkInvalidArray(a)) {

return 0;

}

int result=a[0];

int times=1;

for (int i = 0; i < a.length; i++) {

if (times==0) {

result=a[i];

times=1;

}else {

if (result==a[i]) {

times++;

}else {

times--;

}

}

}

return result;

? ?

}

? ?

private static boolean checkInvalidArray(int[] a) {

if (a == null || a.length == 0) {

return true;

} else {

return false;

}

}

? ?

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] a = { 3, 1, 2, 2, 2, 2, 2, 5, 6 };

// System.out.println(partition(a, 0, a.length - 1));

//????????????????int result = moreThanHalfNum(a, 9);

int result=sol2(a);

System.out.println(result);

//????????????????for (int i : a)

//????????????????????????System.out.println(i);

}

? ?

}