Leetcode No. 169 중수 구하 기

제목 설명
n 크기 의 배열 을 지정 하여 그 중의 중 수 를 찾 습 니 다.중 수 는 배열 에서 발생 하 는 횟수 가 전체 8970 ° n / 2 * 8971 ° 보다 많은 요 소 를 말한다.배열 이 비어 있 지 않다 고 가정 할 수 있 으 며, 주어진 배열 은 항상 다수 가 존재 한다.예시 1:
입력: [3, 2, 3] 출력: 3
예시 2:
입력: [2, 2, 1, 1, 2, 2] 출력: 2
방법 1: 폭력 법
가장 간단 한 방법 은 2 층 순환, 외층 순환 은 하나의 수 를 고정 시 키 고 내부 에서 이 수가 나타 난 총 횟수 를 통계 한다.또한 전체 알고리즘 은 현재 최대 출현 횟수 를 유지 해 야 합 니 다.시간 복잡 도 는 O (n ^ 2) 입 니 다.

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int i=0,j=0;
        int max = -1;
        int majority = -1;  //  
        while(inums.length/2) return majority;
            i=j;
        }
        return -1;
    }

운행 시간 6ms.
방법 2: 해시
배열 을 한 번 옮 겨 다 니 며 HashMap 에 넣 고 이 숫자 가 나타 난 횟수 를 기록 합 니 다.

public int majorityElement(int[] nums) {
        HashMap map = new HashMap<>();
        for(int i=0;i entry: map.entrySet()) 
        {
            int curcount = entry.getValue();
            int curelem = entry.getKey();
            if(maxcount < curcount) {
                maxcount = curcount;
                majority = curelem;
            }
        }
        return majority;
    }

운행 시간 39ms.
방법 3: 중간 아래 표 시 를 취한 다.
배열 을 정렬 한 후, 중 수 는 중간 위치 에 나타난다.

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

방법 4: 랜 덤 프로 세 스
매번 에 무 작위 로 하나의 요 소 를 선택 한 다음 에 이 숫자 가 나타 난 횟수 를 통계 한다. 만약 에 배열 의 길이 의 절반 보다 크 면 중 수 를 찾 았 다 는 것 을 의미한다.여기에 몇 개의 보조 함 수 를 썼 다. 1. [min, max) 의 임 의 수 를 생 성 한다.

private int formRand(Random rand,int min,int max) {
        return rand.nextInt(max-min)+min;  
    }

2. 특정한 요소 의 출현 횟수 를 계산한다.

private int countTime(int[] nums,int target) {
        int count=0;
        for(int i=0;i

3. 주 함수

public int majorityElement(int[] nums) {
        Random rand = new Random();
        int maxcount = nums.length/2;
        while(true) {
            int elem = nums[formRand(rand,0,nums.length)];
            int count = countTime(nums,elem);
            if(count > maxcount) 
                return elem;
        }
    } 

운행 시간 5ms.
방법 5: 분 치 법
분 치 법 사상 을 사용 하면 한 배열 의 중 수 는 왼쪽 부분의 중수 a, 동반 부분의 중수 b 로 이해 할 수 있다. 만약 a = = b 라면 전체 배열 의 중 수 는 a 이다. 그렇지 않 으 면 a 와 b 에서 횟수 가 더 많은 것 을 취한 다. 분 치 법 은 문 제 를 나 누 는데 가장 작은 상황 은 몇 개의 요소 가 하나 남 은 것 이다. 그러면 중 수 는 그 자체 이다.

private int majorityElement(int[] nums,int low,int high)
    {
        if(low==high) return nums[low];
        int mid = (low+high)>>>1;

        int leftElem = majorityElement(nums,low,mid);
        int rightElem = majorityElement(nums,mid+1,high);
        
        if(leftElem==rightElem) return leftElem;

        int countLeft = countTime(nums,low,high,leftElem);
        int countRight = countTime(nums,low,high,rightElem);
        return countLeft>countRight?leftElem:rightElem;
    }

public int majorityElement(int[] nums)
    {
        return majorityElement(nums,0,nums.length-1);
    } 

 private int countTime(int[] nums,int low,int high,int target) {
        int count=0;
        for(int i=low;i<=high;i++)
            if(target == nums[i]) ++count;
        return count;
    }

방법 6: 몰 투표 법 (함께 죽 는 법)
하나의 수열 에서 중수 의 점 수 는 + 1 이 고, 비 중수 의 점 수 는 - 1 이 라 고 가정 하면 전체 수열 의 합 은 0 보다 크다. 이 알고리즘 에서 하나의 득점 count 를 유지 하고, 현재 선택 한 다수 majority 와 유지 합 니 다. 한 라운드 스 캔 을 진행 합 니 다. 스 캔 한 요소 가 현재 중수 와 같 지 않 을 때, - count; 그렇지 않 으 면 + count. count = 0 일 때 중 수 를 바 꿉 니 다.

 public int majorityElement(int[] nums){
         int count = 0;
        int majority = nums[0];
        for(int i=0;i

운행 시간 4ms.