중첩 된 for 루프 사용하지 않기

Question

코드 작성 문제를 해결하고 시간 초과로 많은 수의 입력이있는 테스트 케이스에서 코드가 실패했습니다.

중첩 된 for 루프를 사용하여 순서에 따라 정수 배열의 최소 차이를 찾습니다 (정렬은 옵션이 아닙니다). 예 :이 배열의 최소 차이 : {20, 7, 8, 2, 5}는 ​​(7-5 ​​= 2)이 아닙니다 (8-7 = 1).

중첩 된 for 루프를 사용하면 실행 시간에 문제가 있다는 것을 알고 있습니다. 나는이 경우 중첩 된 for 루프를 사용하는 것에 대한 대안을 많이 찾았으며 어떤 것도 찾지 못했습니다.

중첩 for 루프를 사용하지 않고이 알고리즘을 구현할 수있는 방법이 있습니까?

Answer 1

효율적인 : O는 (N 로그 n)

아이디어는 정렬을 사용하는 것입니다. 아래 단계가 있습니다.

1) 배열을 오름차순으로 정렬하십시오. 병합 또는 빠른 정렬을 사용하는 경우이 단계는 O (n Log n) 시간이 걸립니다.

2) 차이를 무한대로 초기화하십시오. 이 단계는 O (1) 시간이 걸립니다.

3) 정렬 된 배열의 모든 인접 쌍을 비교하고 최소 차이를 추적합니다. 이 단계는 O (n) 시간이 걸립니다.

#include <bits/stdc++.h> 
using namespace std; 


int MinDiff(int arr[], int n) 
{ 
    // Sort array in non-decreasing order 
    sort(arr, arr+n); 

    // Initialize difference as infinite 
    int diff = INT_MAX; 

    // Find the min diff by comparing adjacent 
    // pairs in sorted array 
    for (int i=0; i<n-1; i++) 
     if (arr[i+1] - arr[i] < diff) 
      diff = arr[i+1] - arr[i]; 


    return diff; 
}