配列の出現回数が半分を超える数値-java

配列の出現回数が半分を超える数値-java
方法1:
配列をソートし、中間値は必ず検索する値です.並べ替えの最小時間複雑度(高速並べ替え)O(Nlogn)に,遍歴を加える.
方法2:
ハッシュ・リストを使用する方法は、各配列の出現回数を統計し、出現回数が配列長より大きい数値を出力します.
方法3:
出現回数は配列長の半分を超え,この数字の出現回数が他の数の出現回数の総和よりも多いことを示した.
2つの異なる数を削除するたびに、残りの数のうち、出現回数が総数を超える一般を考慮し、このプロセスを繰り返し、他の数を排除し、最終的にその出現回数が半分を超える数を見つける.この方法の時間的複雑度はO(N)であり,空間的複雑度はO(1)である.
別の考え方では、これは実際の物理削除ではなく、カウントによって実現することができます.配列を巡る過程で、2つの値を保存します.1つは配列の数字で、1つは出現回数です.次の数字をたどると、この数字が前に保存した数字と同じであれば回数に1を加え、異なる場合は回数を1に減らします.回数が0の場合、次の数字を保存して回数を1に設定します.私たちが探している数字が他のすべての数字の合計よりも多く現れるため、探している数字は最後に回数を1に設定したときに対応する数字に違いありません.

    public int MoreHalf(int[] nums) {
        int result = 0;
        int count = 1;
        if (nums.length == 0)
            return -1;
        result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                result = nums[i];
                count = 1;
                continue;
            }
            if (result == nums[i])
                count++;
            else
                count--;
        }
        return result;
    }

方法4:
改良された高速列は、前述したように、1つの配列を並べ替えると、中間位置にある数字が求められる値に違いありません.配列並べ替えの時間的複雑度はO(nlog(n))であるが,この問題に対しては,時間的複雑度O(n)内で求めることができるより良いアルゴリズムがある.
高速ソートアルゴリズムを参考にして、その中のPartition()方法は最も重要な方法であり、この方法はindexを返し、indexの位置の数がソート済みであることを保証することができ、indexの左側の数はindexの数より小さく、indexの右側の数はindexの数より大きい.では、本題はこのような考え方で解くことができます.

はPartition()を介してindexを返し、index=midの場合、配列の中位数が見つかったことを示す.index midの場合、中位数は[start,index-1]の間にあることを示します.最後にindex=midサイクル終了を求めることを知っています.

    public int Partition(int[] nums,int start,int end){
        int pivotkey = nums[start];
        int origin = start;
        while(start<end){
            while(start<end&&nums[end]>=pivotkey) end--;
            while(start<end&&nums[start]<pivotkey) start++;
            swap(nums,start,end);
        }   
        swap(nums,start,end);
        swap(nums,origin,end);
        return end;
    }
    
    public int[] swap(int[] ints, int x, int y) {
        int temp = ints[x];  
        ints[x] = ints[y];  
        ints[y] = temp;  
        return ints;  
    }  
    
    public int MoreThanHalf(int[] nums){
        if(nums.length==0)
            return -1;
        int start = 0;
        int end = nums.length-1;
        int index = Partition(nums, start, end);
        int mid = nums.length/2;
        while(index!=mid){
            if(index>mid)
                //           index  middle，     start index-1     
                index = Partition(nums, start, index-1);
            else{
                //    index+1 end                  
                index = Partition(nums, index+1, end);
            }
        }
        return nums[index];
    }