下文通過幾種方法給大家介紹java數(shù)組數(shù)字出現(xiàn)次數(shù)，具體內(nèi)容如下所示：
方法一：
數(shù)組排序，然后中間值肯定是要查找的值。 排序最小的時間復雜度（快速排序）O(NlogN)，加上遍歷。
方法二：
使用散列表的方式，也就是統(tǒng)計每個數(shù)組出現(xiàn)的次數(shù)，輸出出現(xiàn)次數(shù)大于數(shù)組長度的數(shù)字。
方法三：
出現(xiàn)的次數(shù)超過數(shù)組長度的一半，表明這個數(shù)字出現(xiàn)的次數(shù)比其他數(shù)出現(xiàn)的次數(shù)的總和還多。
考慮每次刪除兩個不同的數(shù)，那么在剩下的數(shù)中，出現(xiàn)的次數(shù)仍然超過總數(shù)的一般，不斷重復該過程，排除掉其他的數(shù)，最終找到那個出現(xiàn)次數(shù)超過一半的數(shù)字。這個方法的時間復雜度是O(N)，空間復雜度是O(1)。
換個思路，這個可以通過計數(shù)實現(xiàn)，而不是真正物理刪除。在遍歷數(shù)組的過程中，保存兩個值，一個是數(shù)組中數(shù)字，一個是出現(xiàn)次數(shù)。當遍歷到下一個數(shù)字時，如果這個數(shù)字跟之前保存的數(shù)字相同，則次數(shù)加1，如果不同，則次數(shù)減1。如果次數(shù)為0，則保存下一個數(shù)字并把次數(shù)設置為1，由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設為1時對應的數(shù)字。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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++;elsecount--;}return result;} |
方法四：
改進的快排，前面提到，如果對一個數(shù)組進行排序，位于中間位置的那個數(shù)字肯定是所求的值。對數(shù)組排序的時間復雜度是O(nlog(n))，但是對于這道題目，還有更好的算法，能夠在時間復雜度O(n)內(nèi)求出。
借鑒快速排序算法，其中的Partition()方法是一個最重要的方法，該方法返回一個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é)束。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
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代碼實現(xiàn)數(shù)字在數(shù)組中出現(xiàn)次數(shù)超過一半的相關內(nèi)容，希望對大家有所幫助！
