Numbers appear in arrays more than half the time based on Java code

Here are some ways to introduce the number of java array Numbers, as shown below:

Method 1:

Array sort, and then the intermediate value must be the value you're looking for. Sort minimum time complexity (quicksort) O(NlogN), plus traversal.

method 2:

Using the hash table method, which counts the number of occurrences of each array, the number of occurrences is greater than the length of the array.

method 3:

The number of occurrences is more than half the length of the array, indicating that this number appears more times than the sum of the other Numbers.

Consider deleting two different Numbers at a time, so that in the remaining Numbers, the number of occurrences is still more than half of the total. The time complexity of this method is O(N) and the space complexity is O(1).

Alternatively, this can be done by counting, rather than physically deleting. As you iterate through the array, you save two values, the number in the array and the number of occurrences. When traversing to the next number, if the number is the same as the saved number, the number is increased by 1, and if it is different, the number is decreased by 1. If the degree is 0, we save the next number and set the degree to 1. Since the number we are looking for appears more times than the sum of all the other Numbers, the number we are looking for must be the same number we found the last time we set the degree to 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;
}

Method 4:

Improved quicksort, as mentioned earlier, if you sort an array, the number in the middle is definitely the value. The time complexity of sorting an array is O(nlog(n)), but for this problem, there is a better algorithm that can figure it out in the time complexity of O(n).

Using the quick sort algorithm as a reference, Partition() method is the most important method. This method returns an index, which can ensure that the Numbers in index position are sorted. The Numbers on the left of index are smaller than those on index, and the Numbers on the right of index are larger than those on index. So we can use this idea to solve this problem.

Returns index via Partition(). If index==mid, then the median of the array is found. If indexmid, the median is between [start, index-1]. Until index==mid, the loop ends.

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)
// If I adjust the array to get it later index Is greater than middle , then continue to adjust start to index-1 Array of extents 
index = Partition(nums, start, index-1);
else{
// Otherwise the adjustment index+1 to end Array of extents  
index = Partition(nums, index+1, end);
}
}
return nums[index];
}

The above content introduced to you Java code to realize the number in the array more than half of the relevant content, I hope to help you!