Count of smaller Numbers After Self 두 가지 사고방식 (더 좋 은 해법 을 연구 하 는 것 을 환영 합 니 다)

말하자면 부 끄 럽 습 니 다. 이미 4 개 월 동안 leetcode 의 문 제 를 자 르 지 않 았 습 니 다.
비록 업무 중 에 고급 알고리즘, 데이터 구 조 를 거의 사용 하지 않 았 지만 저 는 '모든 언어 는 시대 에 뒤떨어 지고 데이터 구조 와 알고리즘 만 영원 할 수 있다' 고 믿 었 습 니 다.leetcode 의 문 제 는 지금까지 137 개 (all solutions) 를 잘 랐 고 6 편의 문제 만 썼 기 때문에 저 는 문 제 를 풀 때 보통 재 미 있 거나 전형 적 인 문제 라 고 생각 합 니 다. 예 를 들 어 이 문제 입 니 다.
제목 링크: 셀 프 후 작은 숫자 개수
이 문 제 는 매우 재 미 있 습 니 다. 하나의 배열 을 제시 하고 새로운 배열 로 돌아 갑 니 다. 새 배열 의 모든 요 소 는 원래 배열 에서 해당 하 는 위치 오른쪽 이 이 요소 보다 작은 요소 의 개 수 를 표시 합 니 다.못 알 아 듣 겠 지?밤 을 들다

   nums = [5, 2, 6, 1]

5     2      5  （2   1）
2     1      2   （1）
6     1      6  （1）
1     0      1  

그래서 배열 로 돌아 갑 니 다.
leetcode 는 조금 좋 지 않 습 니 다. 데이터 크기 범 위 를 주지 않 습 니 다. 그래서 저 는 절대 다수의 사람들 이 저 와 같이 2 층 순환 의 O (n ^ 2) 코드 를 먼저 쓸 것 이 라 고 믿 습 니 다. 제출 하 자마자 시간 이 초과 되 었 습 니 다. 시간 이 초과 되 었 습 니 다. 배열 의 길 이 는 20000 +, O (n ^ 2) 복잡 도 는 몇 억 이 되 었 습 니 다!
이 문 제 를 분석 하려 면 오른쪽 에서 이 숫자 보다 작은 수의 개 수 를 구 해 야 하기 때문에 한 가지 명확 한 것 이 있 습 니 다. 우 리 는 오른쪽 에서 왼쪽으로 배열 을 옮 겨 다 녀 야 합 니 다.아니면 위의 배열 을 예 로 들 면 index = 0 에 옮 겨 다 닐 때 현재 1, 2, 6 개의 데이터 가 있다 는 것 을 알 아야 한다. 우 리 는 데이터 구조 가 필요 하 다. 1, 2, 6 을 저장 할 수 있 고 그 다음 에 5 를 삽입 할 수 있다.
먼저 머 릿 속 에 떠 오 르 는 것 은 트 리 배열 이다.(트 리 배열 을 모 르 는 사람 은 제 가 예전 에 쓴 글 을 참고 할 수 있 습 니 다. [전단 도 데이터 구 조 를 배 워 야 합 니 다] 신기 한 트 리 배열 과 [전단 도 데이터 구 조 를 배 워 야 합 니 다] 신기 한 트 리 배열 의 3 대 응용)
점 을 바 꾸 고 단락 을 구 하 는 것 과 비슷 하 다. 오른쪽 보다 작은 수량 을 구 하 는 것 은 '단락 을 구 하 는 것' 이 고 구 한 후에 이 점 을 삽입 하 는 것 은 '점 을 바 꾸 는 것' 이다.그러나 우 리 는 전통 적 인 나무 모양 의 배열 의 구 해 방향 을 바 꾸 고 배열 요소 의 크기 를 아래 표 로 해 야 한다. 예 를 들 어 A [1] 은 1 의 수량 을 나타 내 는 것 이 고 C [2] 는 1 과 2 의 수량 을 나타 내 는 것 이기 때문에 '개 점' 할 때 증 가 량 이 모두 1 이 고 '큰 인재 가 작은 용도' 라 는 느낌 이 든다.더 아 픈 것 은 데이터 크기 를 모 르 기 때문에 이산 화 를 해 야 한 다 는 점 이다.
목 표 는 [5, 2, 6, 1] 을 [3, 2, 4, 1] 로 바 꾼 다음 나무 모양 배열 로 풀 어 내 는 것 이다.
이산 화 는 먼저 순 서 를 매 긴 다음 에 이산 하고 마지막 에 다시 배열 해 야 한다.

var arr = []
  , len = nums.length;

// array to object
//    index   ，     
for (var i = 0; i < len; i++) {
  var tmp = {};
  tmp.index = i;
  tmp.value = nums[i];
  arr.push(tmp);
}

arr.sort(function(a, b) {
  return a.value - b.value;
});

//    
var maxn = 1;
for (var i = 0; i < len; i++) {
  if (!i) {
    arr[i].nValue = maxn;
  } else {
    arr[i].nValue = arr[i].value === arr[i - 1].value ? maxn : ++maxn;
  }
}

arr.sort(function(a, b) {
  return a.index - b.index;
});

트 리 배열 설명:

//     
var ans = []
  , sum = [];

for (var i = 0; i <= maxn; i++)
  sum[i] = 0;

function lowbit(x) { return x & (-x); }

function update(index, val) {
  for (var i = index; i <= maxn; i += lowbit(i))
    sum[i] += val;
} 

function getSum(index) {
  var ans = 0;
  for (var i = index; i; i -= lowbit(i))
    ans += sum[i];
  return ans;
}

for (var i = len - 1; i >= 0; i--) {
  var nValue = arr[i].nValue;
  ans.unshift(getSum(nValue - 1));
  update(nValue, 1);
}

트 리 배열 부분 은 간단 한 업데이트 와 조회 입 니 다.전체 코드 는 트 리 배열 해법 을 참고 할 수 있 습 니 다.
Accept 에 도 불구 하고 300 ms + 가 걸 렸 다. 35% 에 불과 한 자 바스 크 립 트 솔 루 션 을 꺾 었 다. 가장 좋 은 답 은 200 ms 안팎 이 었 다. O (n) 의 해법 이 있 는 지 의 심 스 러 웠 지만 4 번 의 nlogn 인지 아 닌 지 생각 하지 못 했다.
아니면 [5, 2, 6, 1] 을 예 로 들 어 매 거 진 5 시 에 [1, 2, 6] 중 소 5 의 수량 을 요구 하 는 동시에 5 를 꽂 아서 이 진 검색 트 리 (BST) 를 유지 하 는 것 이 가능 한 것 같 습 니까?아니 야, 아니 야, 이 건 적나라한 2 점 찾기 아니 야!!!
2 분 은 [1, 2, 6] 중 소 5 의 개 수 를 찾 고 검사 한 후에 5 를 배열 에 넣 어 배열 의 단조 성 을 유지 하 며 자바 script 은 마침 splice () 방법 으로 하나의 숫자 를 배열 에 삽입 할 수 있다.
2 분 부분 은 target 보다 적은 수량 을 되 돌려 주 는 동시에 target 을 삽입 하 는 위치 (index) 입 니 다.

// binary search
function bSearch(target, a) {
  var start = 0
    , end = a.length - 1;

  while(start <= end) {
    var mid = ~~((start + end) >> 1);
    if (a[mid] >= target)
      end = mid - 1;
    else if (a[mid] < target)
      start = mid + 1;
  }

  return start;
}

전체 코드 는 2 분 검색 해법 을 참고 할 수 있다.
그러나 안 타 깝 게 도 4 번 nlogn 에서 1 번 nlongn 으로 떨 어 졌 음 에 도 불구 하고 시간 이 걸 리 지 않 고 반등 했다. 그 이 유 를 따 져 보면 unshift () 방법 과 splice () 방법의 대량 호출 이 라 고 생각 합 니 다. 어떻게 생각 하 세 요?
개인 은 잠시 O (n) 의 선형 해법 (없 을 수도 있 습 니 다) 을 생각해 내지 못 했 지만 실제로 200 ms 의 자바 script solution 이 있 습 니 다. BST 입 니까?생각 있 는 학우 들 이 나 와 교류 하고 토론 하 는 것 을 환영한다.