寻找出现次数过半的元素-在线编程-K6K4.com

给定一个整数数组，求数组中出现次数超过数组长度一半的元素。
要求：时间复杂度为O(n)

输入、输出描述

输入：

arr: 非空整数数组

输出：

数组中出现次数超过数组长度一半的元素

Example

输入：

arr=[1,2,2,3,2]

输出：

代码：

import java.util.*;

public class Main {

  public int partion(int a[],int low,int high){
	int key = a[low];
	while (low<high)
	{
		while(low<high && a[high]>=key){
			high--;
		}
		if(low<high){
			a[low++] = a[high];
		}

		while(low<high && a[low]<=key){
			low++;
		}
		if(low<high){
			a[high--] = a[low];
		}
	}
	a[low] = key;
	return low;
}

public int func(int a[],int n){

	int start,end,mid;
	mid = n/2;
	start = 0;
	end = n-1;
	int index = partion(a,start,end);

	while (index != mid)
	{
		if (index > mid)
		{
			end = index - 1;
			index = partion(a,start,end);
		}
		else
		{
			start = index + 1;
			index = partion(a,start,end);
		}
	}

	int c = 0;
	for (int i=0;i<n;i++)
	{
		if (a[i] == a[index])
		{
			 c++;
		}
	}
	if (c > mid)
	{
		return a[index];
	}
	else
	{
		return -1;
	}
}
  
public int solution(int[] arr,int n) {
		//Arrays.sort(arr);
  		return func(arr,n);
    }
}