The following is a few methods to introduce the number of java array numbers to you. The specific content is as follows:
Method 1:
Array sorting, and then the intermediate value is definitely the value to be found. Sort the minimum time complexity (quick sort) O(NlogN), plus traversal.
Method 2:
Using a hash table method, that is, counting the number of occurrences of each array and outputting numbers whose occurrences are greater than the length of the array.
Method 3:
The number of occurrences exceeds half of the length of the array, indicating that this number appears more times than the sum of other numbers.
Consider deleting two different numbers each time, the number of occurrences in the remaining numbers still exceeds the total number. Repeat the process constantly, exclude other numbers, and finally find the number with more than half of the occurrences. The time complexity of this method is O(N) and the space complexity is O(1).
To change the idea, this can be achieved through counting, rather than real physical deletion. During the process of traversing the array, save two values, one is the number in the array and the other is the number of occurrences. When traversing to the next number, if this number is the same as the previously saved number, the number of times is increased by 1, and if it is different, the number of times is decreased by 1. If the number of times is 0, save the next number and set the number to 1. Since the number we are looking for appears more times than the sum of all other numbers, the number we are looking for must be the corresponding number when the number of times is set to 1 the last time.
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;}Method 4:
Improved quick-row sorting, mentioned earlier, if an array is sorted, the number in the middle position must be the value you want. The time complexity of sorting arrays is O(nlog(n)), but for this question, there are better algorithms that can be found within the time complexity O(n).
Deriving from the quick sorting algorithm, the Partition() method is the most important method. This method returns an index, which can ensure that the number at the index position is sorted. The number on the left of the index is smaller than the number where the index is located, and the number on the right of the index is larger than the number where the index is located. Then this question can be solved using this idea.
Return index via Partition(). If index==mid, it means that the median of the array has been found; if indexmid, it means that the median is between [start, index-1]. I know that the end of the index==mid loop is obtained.
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;}p 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)//If the index obtained after adjusting the array is greater than middle, continue to adjust the array index of start to index-1 section = Partition(nums, start, index-1);else{//Otherwise adjust the array index of index+1 to end section = Partition(nums, index+1, end);}}return nums[index];}The above content introduces the relevant content of Java code that implements numbers appearing more than half of the times in an array. I hope it will be helpful to everyone!