순서 배열 의 단일 요소

4753 단어 알고리즘
제목.
난이도 중간 에 정수 만 포함 하 는 질서 있 는 배열 을 정 하고 모든 요 소 는 두 번 씩 나타 나 며 한 번 만 나타 나 이 수 를 찾 습 니 다.메모: 프로젝트 는 O (log n) 시간 복잡 도와 O (1) 공간 복잡 도 에서 실행 되 어야 합 니 다.
  : [1,1,2,3,3,4,4,8,8]
  : 2

분석 하 다.
  • 배열 의 길 이 는 틀림없이 홀수
    • 이다.
  • 이분법 사용
  • 배열 은 하나의 요소 (mid) 를 줄 이 고 나머지 는 짝수 로 나 누 어 반 으로 나 누 거나 모두 짝수
    • 이다.
  • 이분법 에서 이 몇 개의 조합 일 수 있 습 니 다. 만약 에 mid 가 짝수 라면 (반드시 그것 을) 첫 번 째 것 이 고 반쪽 이 짝수 이기 때문에 이쪽 에 남 은 것 은 홀수 입 니 다. 그 수 는 반드시 이 안에 있 습 니 다. 그렇지 않 으 면 mid 또는 mid 이전의 수 
     1 2 2
 2 2 3 
 1 2 3
    코드 는 다음 과 같 습 니 다 
    class Solution {
    public int singleNonDuplicate(int[] nums) {
        int head = 0;
        int tail = nums.length - 1;
        while (head < tail) {
            int mid = head + (tail - head) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) {
                head = mid + 2;
            } else {
                tail = mid;
            }
        }
        return nums[head];
    }
}
    • 프로 그래 밍 의 아름다움 - 하위 배열 의 최대 곱 하기
    최대 하위 배열 의 합

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage