下文通過幾種方法給大家介紹java數(shù)組數(shù)字出現(xiàn)次數(shù)，具體內(nèi)容如下所示：

方法一：

數(shù)組排序，然后中間值肯定是要查找的值。 排序最小的時(shí)間復(fù)雜度（快速排序）O(NlogN)，加上遍歷。

方法二：

使用散列表的方式，也就是統(tǒng)計(jì)每個(gè)數(shù)組出現(xiàn)的次數(shù)，輸出出現(xiàn)次數(shù)大于數(shù)組長度的數(shù)字。

方法三：

出現(xiàn)的次數(shù)超過數(shù)組長度的一半，表明這個(gè)數(shù)字出現(xiàn)的次數(shù)比其他數(shù)出現(xiàn)的次數(shù)的總和還多。

考慮每次刪除兩個(gè)不同的數(shù)，那么在剩下的數(shù)中，出現(xiàn)的次數(shù)仍然超過總數(shù)的一般，不斷重復(fù)該過程，排除掉其他的數(shù)，最終找到那個(gè)出現(xiàn)次數(shù)超過一半的數(shù)字。這個(gè)方法的時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是O(1)。

換個(gè)思路，這個(gè)可以通過計(jì)數(shù)實(shí)現(xiàn)，而不是真正物理刪除。在遍歷數(shù)組的過程中，保存兩個(gè)值，一個(gè)是數(shù)組中數(shù)字，一個(gè)是出現(xiàn)次數(shù)。當(dāng)遍歷到下一個(gè)數(shù)字時(shí)，如果這個(gè)數(shù)字跟之前保存的數(shù)字相同，則次數(shù)加1，如果不同，則次數(shù)減1。如果次數(shù)為0，則保存下一個(gè)數(shù)字并把次數(shù)設(shè)置為1，由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的數(shù)字。

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;
}

方法四：

改進(jìn)的快排，前面提到，如果對(duì)一個(gè)數(shù)組進(jìn)行排序，位于中間位置的那個(gè)數(shù)字肯定是所求的值。對(duì)數(shù)組排序的時(shí)間復(fù)雜度是O(nlog(n))，但是對(duì)于這道題目，還有更好的算法，能夠在時(shí)間復(fù)雜度O(n)內(nèi)求出。

借鑒快速排序算法，其中的Partition()方法是一個(gè)最重要的方法，該方法返回一個(gè)index，能夠保證index位置的數(shù)是已排序完成的，在index左邊的數(shù)都比index所在的數(shù)小，在index右邊的數(shù)都比index所在的數(shù)大。那么本題就可以利用這樣的思路來解。

通過Partition()返回index，如果index==mid，那么就表明找到了數(shù)組的中位數(shù)；如果indexmid，表明中位數(shù)在[start,index-1]之間。知道最后求得index==mid循環(huán)結(jié)束。

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)
//如果調(diào)整數(shù)組以后獲得的index大于middle，則繼續(xù)調(diào)整start到index-1區(qū)段的數(shù)組
index = Partition(nums, start, index-1);
else{
//否則調(diào)整index+1到end區(qū)段的數(shù)組 
index = Partition(nums, index+1, end);
}
}
return nums[index];
}

以上內(nèi)容給大家介紹了Java代碼實(shí)現(xiàn)數(shù)字在數(shù)組中出現(xiàn)次數(shù)超過一半的相關(guān)內(nèi)容，希望對(duì)大家有所幫助！

最新評(píng)論