基於Java代碼完成數字在數組中湧現次數跨越一半。本站提示廣大學習愛好者：（基於Java代碼完成數字在數組中湧現次數跨越一半）文章只能為提供參考，不一定能成為您想要的結果。以下是基於Java代碼完成數字在數組中湧現次數跨越一半正文
下文經由過程幾種辦法給年夜家引見java數組數字湧現次數，詳細內容以下所示：
辦法一：
數組排序，然後中央值確定是要查找的值。 排序最小的時光龐雜度（疾速排序）O(NlogN)，加上遍歷。
辦法二：
應用散列表的方法，也就是統計每一個數組湧現的次數，輸入湧現次數年夜於數組長度的數字。
辦法三：
湧現的次數跨越數組長度的一半，注解這個數字湧現的次數比其他數湧現的次數的總和還多。
斟酌每次刪除兩個分歧的數，那末在剩下的數中，湧現的次數依然跨越總數的普通，赓續反復該進程，消除失落其他的數，終究找到誰人湧現次數跨越一半的數字。這個辦法的時光龐雜度是O(N)，空間龐雜度是O(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;
}
辦法四：
改良的快排，後面提到，假如對一個數組停止排序，位於中央地位的誰人數字確定是所求的值。對數組排序的時光龐雜度是O(nlog(n))，然則關於這道標題，還有更好的算法，可以或許在時光龐雜度O(n)內求出。
自創疾速排序算法，個中的Partition()辦法是一個最主要的辦法，該辦法前往一個index，可以或許包管index地位的數是已排序完成的，在index右邊的數都比index地點的數小，在index左邊的數都比index地點的數年夜。那末本題便可以應用如許的思緒來解。
經由過程Partition()前往index，假如index==mid，那末就注解找到了數組的中位數；假如indexmid，注解中位數在[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];
}
以上內容給年夜家引見了Java代碼完成數字在數組中湧現次數跨越一半的相干內容，願望對年夜家有所贊助！
