优化时间和空间效率

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

//解法一：直观解法，先排序
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int half=array.length/2;
        int count=0;
        for(int i=0;i<array.length;i++)
        {
            if(array[i]==array[half])
                count++;
        }
        if(count>half)
            return array[half];
        else
            return 0;
    }
}
//解法二：根据数组特点找出时间复杂度为O(n)的算法
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0)
            return 0;
        int times=1;
        int result=array[0];
        for(int i=1;i<array.length;i++)
        {
            if(times==0)
            {
                result=array[i];
                times=1;
            }
            else if(result==array[i])
                times++;
            else
                times--;
        }
        //判断是否有出现次数超过一半的数字
        int t=0;
        for(int i=0;i<array.length;i++)
        {
            if(array[i]==result)
                t++;
        }
        if(t*2>array.length)
            return result;
        else
            return 0;
    }
}

最小的k个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
示例1
输入：[4,5,1,6,2,7,3,8],4
返回值：[1,2,3,4]

import java.util.ArrayList;
import java.lang.Math;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> a=new ArrayList<>();
        if(input.length<k || k<=0)
            return a;
        int length=input.length;
        int start=0;
        int end=length-1;
        int index=Partion(input,start,end);
        while(index!=k-1)
        {
            System.out.println(index);
            if(index>k-1)
            {
                index=Partion(input,start,index-1);
            }
            if(index<k-1)
            {
                index=Partion(input,index+1,end);
            }
        }
        for(int i=0;i<k;i++)
        {
            a.add(input[i]);
        }
        return a;
    }
    public int Partion(int [] input ,int start,int end)
    {
        int length=end-start+1;
        int index=(int)Math.random()*(length)+start;
        Swap(input,index,end);
        int small=start-1;
        int e=input[end];
        for(int i=start;i<end;i++)
        {
            int in=input[i];
            if(input[i]<input[end])
            {
                small++;
                System.out.println(small);
                if(small!=i)
                {
                    Swap(input,small,i);
                }
            }
        }
        small++;
        Swap(input,small,end);
        return small;
    }
    public void Swap(int[] input,int a,int b)
    {
        int t=input[a];
        input[a]=input[b];
        input[b]=t;
    }
}