시퀀스 Leetcode 솔루션에서 산술 진행 가능

난이도 쉽게
자주 묻는 질문 아마존
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 정렬조회수 77

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명

”Can Make Arithmetic Progression From Sequence”문제에서 배열이 주어 졌는데, 이제 우리는 산술 진행 순서를 재정렬하여.

arr = [3,1,5]
true

설명 : 우리는 배열을 {1,3,5 / 2}로 재 배열 할 수 있으며, 이는 공통 차이가 XNUMX 인 산술 진행을 형성하므로 출력이 참입니다.

시퀀스 Leetcode 솔루션에서 Can Make Arithmetic Progression에 대한 접근 방식

산술 시리즈는 인접한 숫자의 차이가 일정한 시리즈입니다. 매우 기본적인 접근 방식은 배열을 정렬하고 인접한 요소 간의 차이를 확인하는 것입니다. 차이가 모든 연속 쌍에 대해 동일하면 산술 진행이고 그렇지 않으면 산술 진행이 아닙니다.

시퀀스 Leetcode 솔루션에서 산술 진행 가능

정렬을위한 시간 복잡성은 nlogn입니다. 배열에 대한 조회 테이블을 만들어 시간 복잡성을 개선 할 수 있습니다.

AP의 n 번째 항은 = a + (n-1) * d이며, 여기서 a는 시리즈의 첫 번째 요소, n은 요소의 수, d는 공통 차이입니다.

AP의 최소 요소는 = a이고

AP의 최대 요소는 = a + (n-1) * d이므로

d = (최대-최소) / (n-1).

  1. 배열의 최소 및 최대 요소를 찾을 수 있습니다. 이를 사용하여 d (공통 차)를 계산할 수 있습니다.
  2. 배열에 대한 조회 테이블을 만듭니다.
  3. 이제 우리는 첫 번째 요소와 공통 차이점을 알고 있습니다.
  4. a와 d로 구성된 산술 시리즈의 모든 n 요소가 룩업 테이블에 있는지 확인합니다.
  5. 모든 요소가 룩업 테이블에 있으면 시퀀스에서 산술 진행을 만들 수 있습니다. 그렇지 않으면 시퀀스에서 산술 진행을 만들 수 없습니다.

실시

시퀀스에서 산술 진행을 만들 수있는 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
  bool canMakeArithmeticProgression(vector<int>& arr) {
  unordered_set<int> seen;
  int mi = INT_MAX, mx = INT_MIN, n = arr.size();
        for (int a : arr) {
            mi = min(mi, a);
            mx = max(mx, a);
            seen.insert(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (seen.find(mi)==seen.end()) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
int main() 
{ 
 vector<int> arr = {3,5,1}; 
 cout <<boolalpha;   
 cout<<canMakeArithmeticProgression(arr)<<endl; 
 return 0;
}
true

시퀀스에서 산술 진행을 만들 수있는 Java 코드

import java.util.*; 
public class Tutorialcup {
 public static boolean canMakeArithmeticProgression(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
        for (int a : arr) {
            mi = Math.min(mi, a);
            mx = Math.max(mx, a);
            seen.add(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (!seen.contains(mi)) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
  public static void main(String[] args) {
    int [] arr = {3,5,1}; 
    System.out.println( canMakeArithmeticProgression(arr));
  }
}
true

시퀀스 Leetcode 솔루션에서 산술 진행을 만들 수있는 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 배열을 순회하여 조회 테이블을 만들고 산술 시리즈의 모든 요소가 조회 테이블에 있는지 확인하기 때문입니다. 여기서 n은 입력 배열의 크기입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (N) 배열에 대한 조회 테이블을 만들고 있기 때문입니다. 여기서 n은 입력 배열의 크기입니다.

참조

균열 시스템 설계 인터뷰
Translate »