[면접 문제] 두 배열 의 차 이 를 구하 세 요. 절대 치가 가장 작은 값 입 니 다.

제목 설명:
하나의 정수 배열 이 있 습 니 다. 두 개의 차 이 는 절대 값 이 가장 작은 값 을 요청 합 니 다. 최소 값 만 구하 면 됩 니 다. 어느 두 개의 수 를 구하 지 마 십시오.
두 가지 일반적인 사고방식:
이 문 제 를 푸 는 일반적인 사 고 는 무엇 입 니까?문 제 를 관찰 한 결과 나 는 뒤에 두 개의 수 를 구하 지 말 라 고 강조 했다. 그러면 가장 간단 한 O (n ^ 2) 의 알고리즘 은 분명히 많은 공 부 를 하지 않 았 다.응, 좋아, 이 방법 이 안 되면 다른 것 을 생각해 봐.배열, 즉 서열 과 같은 문제 에 대해 자주 사용 하 는 사고 가 있 는데 그것 이 바로 예비 처리 이다.이 문 제 는 될 것 같다.
먼저, 배열 에 대해 순 서 를 매 길 수 있 습 니 다. 이것 은 O (n * logn) 시간 과 같은 해결 을 할 수 있 습 니 다. 그리고 이 예비 처리 가 있 으 면 절대 치 의 차이 최소 치 는 반드시 예비 처 리 된 배열 뒤의 인접 한 요소 에서 만 발생 할 것 이 라 고 생각 합 니 다. 이것 은 분명 한 사실 입 니 다.그러면 우 리 는 배열 을 한 번 순환 하여 두 두 사이 의 절대 치 의 최소 치 를 기록 할 수 있다. 그러면 원 하 는 값 은 바로 해답 이 고 전체적인 시간 복잡 도 는 O (n * logn) 이다.이런 방법 을 자세히 생각해 보면 순서 가 우리 가 찾 아야 할 공간 을 줄 이 고 시간 복잡 도 를 줄 이 는 목적 을 달성 한 것 이 분명 하 다.그러나 이 해법 은 여전히 만 족 스 럽 지 못 하 다. 왜냐하면 우 리 는 시간 을 낭비 하여 최종 적 인 두 가지 요 소 를 구 했 기 때문에 제목 은 요구 하지 않 기 때문에 이것 은 틀림없이 가장 좋 은 것 이 아니다.
삼 전환 의 사상
문 제 를 자세히 살 펴 보면 가장 좋 은 해 는 최소 치 만 구하 고 구체 적 인 요 소 를 구하 지 않 는 것 이 어야 한 다 는 것 을 알 수 있다. 그러면 어떻게 해 야 할 까?우 리 는 보조 수 조 를 쓸 생각 은 할 수 있 지만, 이 보 조 를 어떻게 할 지 는 생각 하기 어렵다.사실 이 문 제 는 저 는 일반적인 사 고 를 통 해 이 가장 좋 은 문 제 를 어떻게 생각 하 는 지 계속 생각 했 습 니 다. 그러나 저 는 그 당시 에 생각 하지 못 했 습 니 다. 이것 이 바로 제 가 이 블 로 그 를 쓴 이유 입 니 다. 즉, 저 로 하여 금 이런 생각 을 이해 하고 인상 깊 게 하 게 하 는 것 입 니 다. 그러나 이것 은 이 문 제 를 풀 거나 이런 방법 을 연상 시 킬 수 있 는 문제 에 만 적 용 될 수 있 습 니 다. 이 뒤에 더욱 일반적인 사고 가 있 습 니 다.(전환 이 라 고 할 수 있 지만 좀 더 구체 적 으로 할 수 있다) 저 는 생각 지도 못 했 습 니 다. 생각 나 는 친구 들 이 저 에 게 연락 하 기 를 바 랍 니 다!
자, 본 문제 에서 해 야 할 보조 배열 은 이러한 배열 입 니 다. Bn 으로 설정 합 니 다. 원래 문제 에서 주어진 배열 은 An 이 고 Bn 은 다음 과 같 습 니 다.
　　B1 = A1 - A2;
　　B2 = A2 - A3;
　　B3 = A3 - A4;
　　......
　　Bn-1 = An-1 - An.
주의 하 세 요. Bn 의 길 이 는 n - 1 입 니 다. An 보다 한 명 작 습 니 다. 똑똑 한 학생 들 은 이 보조 배열 을 보면 바로 이 유 를 알 수 있 습 니 다. 이렇게 하면 우 리 는 손 쓸 수 없 을 것 처럼 보 이 는 이 문 제 를 Bn 의 절대 치 를 구 하 는 가장 작은 최 장 연속 서브 서열 과 바 꿀 수 있 습 니 다. 왜냐하면 Bn 의 연속 서브 서열 과 An 의 임 의 두 수의 차이 이기 때 문 입 니 다.(주의해 야 할 것 은 제목 이 절대 치가 가장 작 기 때문에 A1 - A2 를 구 하 는 것 은 A2 - A1 을 구 하 는 것 과 같다). 예 를 들 어:
　　A2 - A5 = B2 + B3 + B4 = A2 - A3 + A3 - A4 + A4 - A5 = A2 - A5
실제로 모든 Ai - Aj (i < j) = sigma (k = i - > k = j - 1) (k)
이렇게 되면 우 리 는 문 제 를 연속 서브 시퀀스 문제 로 전환 시 키 는 데 성공 할 수 있 습 니 다. 그러나 우리 가 예전 에 했 던 최대 또는 최소 연속 서브 시퀀스 와 완전히 다 릅 니 다. 여 기 는 절대 치가 가장 작 습 니 다. 그러면 어떤 값 이 절대 치가 가장 작 을 수 있 습 니까? 양수 가 가장 작 거나 마이너스 가 가장 클 수 있 습 니 다. 즉, 축 에서 0 보다 가 까 운 수 는 절대 치가 더 작 습 니 다. 이 를 바탕 으로 우 리 는 할 수 있 습 니 다.다음 과 같은 방법 을 얻 을 수 있 습 니 다.
원래 의 최대 연속 자 서열 과 마찬가지 로 수학 귀납법 으로 생각 하고 우 리 는 귀납 적 기 초 를 직접 보아 야 한다.
귀납 적 기초: 이미 알 고 있 는 B1. Bk 의 절대 치 최소 연속 의 연속 서브 시퀀스 와 Min (Bk) 을 가정 합 니 다.
우 리 는 이 구 해 B (k + 1) 를 이용 하여 B (k + 1) 를 넣 으 면 Min (Bk) 보다 작은 것 은 B (k + 1) 로 끝 나 는 절대 값 이 가장 작은 연속 서브 시퀀스 와 이것 을 Min (Bk) 과 비교 하면 Min (Bk) 을 업데이트 해 야 하 는 지 알 수 있 기 때문에 이 귀납 적 기반 을 강화 합 니 다.
더 강 한 귀납 적 기초: 이미 알 고 있 는 B1. Bk 의 절대 치 최소 연속 의 연속 서브 시퀀스 와 Min (Bk), 그리고 Bk 로 끝 나 는 절대 치 최소 연속 서브 시퀀스 와 Suffix (Bk) 를 가정 합 니 다.
이 요약 이 있 으 면, 우 리 는 이 Suffix (Bk) 를 어떻게 유지 할 것 인 가 를 생각 할 수 있 습 니 다. 목 표 는 Suffix (B (k + 1) 를 B (k + 1) 로 끝 나 는 최소 연속 서브 시퀀스 와 유지 하 는 것 입 니 다. 최소 화 를 추구 하 는 사고방식 에 따 르 면, Suffix (Bk) 가 정수 라면 0 으로 두 는 것 입 니 다. 정수 라면, 후속 적 으로 Suffix (B (k + 1) 를 구하 기 때 문 입 니 다.시 는 0 을 사용 하 는 것 보다 더 클 것 입 니 다. 정 수 는 전체 값 을 크게 만 들 기 때 문 입 니 다. 0 은 그렇지 않 습 니 다. 마찬가지 로 우 리 는 Suffix 를 구 할 때 직접 0 을 설치 하 는 것 보다 더 작 게 만 들 면 됩 니 다. 그렇지 않 으 면 우 리 는 Suffix (B (k + 1) 를 직접 사용 할 수 있 습 니 다.0 을 두 면 더 작은 값 을 얻 을 수 있 습 니 다. 절대 값 이 가장 작 기 때문에 최소 값 으로 생각 하 는 것 은 안 됩 니 다. 어떤 Suffix 가 일시 적 으로 아주 작은 음 수 를 구 할 수 있 기 때문에 다음 에 어떤 정 수 를 더 하면 아주 작은 정수 가 될 수 있 기 때문에 양수 마이너스 로 결론 을 내 릴 수 없 기 때문에 0 과 의 거 리 를 비교 하 는 방법 을 취해 야 합 니 다. 만약 에 기 호 를 비교 하 는 방법 을 취해 야 합 니 다.앞의 suffix 는 다음 수의 기호 와 반대 되 므 로 다음 suffix 를 계속 구 할 수 있 습 니 다. 우 리 는 절대적 으로 더 작은 suffix 를 얻 을 수 있 기 때 문 입 니 다. 같은 번호 라면 양음 을 막론하고 현재 suffix 를 0 으로 설정 하 는 것 보다 더 나 쁠 것 입 니 다. 왜냐하면 다음 의 suffix 는 수축 에서 0 에서 더 멀 어 질 것 입 니 다. 그래서 우 리 는 Suffix 를 유지 하 는 공식 은 다음 과 같 습 니 다.
　　Suffix(B(k+1)) = Suffix(B(k)) + B(k+1）， if (Suffix(B(k))*B(k+1)) < 0
　　Suffix(B(k+1)) = 0, if (Suffix(B(k))*B(k+1)) ) > 0
이렇게 해서 우 리 는 계속 귀납 하면 최종 Min (Bn) 을 구 할 수 있 고 해 를 구 할 수 있다. 전체 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (n) 이다.
네 가지 절차
프로그램 은 다음 과 같 습 니 다:
　　

1 //TestAlgo.cpp : Defines the entry point for the console application.
2 //
3 
4 
5 #include"stdafx.h"
6 
7 #include<iostream>
8 #include<cmath>
9 usingnamespacestd;
10 
11 intGetMinAbsoluteSubsequence(intB[],intnLen)
12 {
13 intnGlobal=INT_MAX;
14 
15 intnSuffix=0;
16 
17 for(inti=0; i<nLen; i++)
18 {
19 nSuffix+=B[i];
20 
21 if(abs(nSuffix)<abs(nGlobal))
22 {
23 nGlobal=nSuffix;
24 }
25 
26 
27 if(i+1<nLen)
28 {
29 if(nSuffix*B[i+1]>0)
30 nSuffix=0;
31 }
32 }
33 
34 returnabs(nGlobal);
35 }
36 
37 intGetMinAbsoluteDiff(intA[],intnLen)
38 {
39 //create aid array
40 int*b=newint[nLen-1];
41 memset(b,0,sizeof(b[0])*(nLen-1));
42 for(inti=0; i<nLen-1; i++)
43 {
44 b[i]=A[i]-A[i+1];
45 }
46 
47 returnGetMinAbsoluteSubsequence(b,nLen-1);
48 }
49 
50 int_tmain(intargc, _TCHAR*argv[])
51 {
52 intA[]={1,20,200,16,13};
53 intnLen=5;
54 
55 cout<<GetMinAbsoluteDiff(A,nLen);
56 
57 getchar();
58 return0;
59 }

　　　　
다섯 가지 총결산
전체적인 사고 과정 이 바로 이렇다. 전체적으로 보면 이런 문 제 는 사고 가치 가 있다. 적어도 우 리 는 각종 미 를 느 꼈 고 전환 의 의 미 를 깊이 이해 할 수 있다.