내림차순으로 정렬되지 않은 nums라는 배열과 숫자 대상이 있다고 가정합니다. 대상이 다수 요소인지 찾아야 합니다. 배열에서 다수 요소는 길이가 N인 배열에서 N/2번 이상 나타나는 요소입니다. 따라서 배열이 다음과 같다면 - [2,4,5,5,5,5,5,6,6] target은 5이고 출력은 true입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- lower() 및 upper()의 두 가지 지원 모듈이 있습니다. 다음과 같습니다.
- lower()는 두 개의 인수 배열 arr과 target을 취합니다. 즉 -
- 낮음 :=0, 높음 :=arr의 길이
- 낮음 <높음 −
- 중간 :=낮음 + (높음 - 낮음)/2
- arr[mid] =target이면 high =mid, 그렇지 않으면 low =mid + 1
- arr[high] =target이면 high를 반환하고, 그렇지 않으면 -1을 반환합니다.
- upper()는 두 개의 인수 배열 arr과 target을 취합니다. 즉 -
- 낮음 =0, 높음 =arr의 길이
- 낮음 <높음 −
- 중간 =낮음 + (높음 - 낮음)/2
- arr[mid] =target이면 low =mid, 그렇지 않으면 high =mid - 1
- arr[low] =target이면 로우를 반환하고, 그렇지 않으면 -1을 반환합니다.
- 주요 기능은 다음과 같습니다 -
- u :=상위(arr, 대상)
- l :=lower(arr, target)
- u – l + 1> (숫자의 길이)일 때 true를 반환 / u가 -1이 아니면 2, 그렇지 않으면 false
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def upper(self,n,target): low = 0 high = len(n)-1 while low<high: mid = low + (high - low + 1)//2 if n[mid] == target: low = mid else: high = mid-1 return low if n[low] == target else -1 def lower(self,n,target): low = 0 high = len(n)-1 while low < high: mid = low + (high - low)//2 if n[mid]== target: high = mid else : low = mid +1 return high if n[high] == target else -1 def isMajorityElement(self, nums, target): u = self.upper(nums,target) l = self.lower(nums,target) return u-l+1 >len(nums)/2 if u != -1 else False ob1 = Solution() print(ob1.isMajorityElement([2,4,5,5,5,5,5,6,6], 5))
입력
[2,4,5,5,5,5,5,6,6] 5
출력
true