자바 코드 기반 숫자 구현 그룹 발생 횟수 절반 이상

다음은 몇 가지 방법을 통해 여러분에게 자바 수조 숫자의 출현 횟수를 소개합니다. 구체적인 내용은 다음과 같습니다.
방법 1:
그룹 정렬, 그리고 중간 값은 틀림없이 찾을 값입니다.정렬의 최소 시간 복잡도(빠른 정렬) O(NlogN)
방법 2:
산목록을 사용하는 방식, 즉 모든 수조가 나타나는 횟수를 통계하고 출력 발생 횟수가 수조의 길이보다 많은 숫자를 출력한다.
방법 3:
출현 횟수가 수조의 길이의 절반을 초과한 것은 이 숫자가 출현한 횟수가 다른 숫자가 출현한 횟수의 총계보다 더 많다는 것을 나타낸다.
매번 두 개의 다른 수를 삭제하는 것을 고려하면 나머지 수에서 나타나는 횟수는 여전히 총수를 초과하는 일반적이다. 이 과정을 끊임없이 반복하고 다른 수를 배제하고 최종적으로 그 나타나는 횟수가 절반을 넘는 숫자를 찾아낸다.이 방법의 시간 복잡도는 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;
}

방법 4:
개선된 빠른 배열, 앞에서 언급한 바와 같이, 만약 하나의 그룹을 정렬한다면, 중간 위치에 있는 그 숫자는 틀림없이 원하는 값이다.수조 정렬의 시간 복잡도는 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];
}

이상의 내용은 자바 코드 구현 숫자가 그룹에서 발생하는 횟수가 절반을 넘는 관련 내용을 소개해 드리니 도움이 되었으면 합니다!