面经上一个题及解法

cpcs

( J; L) [: x0 V, n
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。


. A, X( o, E6 `Integer V lies strictly between integers U and W if U < V < W or if U > V > W.


A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 = P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q], and in addition A[P] ≠ A[Q].
$ z7 `7 G; T3 ]
7 M/ W: b- J5 Z8 g. _/ r
For example, in array A such that:
( p4 E1 l$ q6 s) VA[0] = 0
A[1] = 3
+ q/ V) U1 L% \8 [! XA[2] = 3
4 O3 Q- `0 @0 M6 n9 q6 WA[3] = 7
( B  N6 C- E2 t) |A[4] = 5
A[5] = 3
) v& b0 o3 g  W$ u, h1 A* DA[6] = 11
A[7] = 1
+ I5 o) A8 k" _% c, _4 |the following pairs of indices have adjacent values:
; z2 f& `' `/ U# ^) ^, R
' P0 u% y0 Z# V  H+ _- a7 w
(0, 7), (1, 4), (1, 7),
$ o% `+ t. l7 M6 u$ M(2, 4), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
5 ?3 G/ X# U2 x/ `# {For example, indices 4 and 5 have adjacent values because the values A[4] = 5 and A[5] = 3 are different, and there is no value in array A that lies strictly between them - the only such value could be the number 4, which is not present in the array.


Given two indices P and Q, their distance is defined as abs(P-Q), where abs(X) = X for X >= 0, and abs(X) = -X for X < 0. For example, the distance between indices 4 and 5 is 1 because abs(4 - 5) = (5 - 4) = 1.
2 M$ C" b9 x$ Z+ X/ `
( i3 n! A& ^/ n! T6 Y: _$ N4 g
Write a function:
9 o1 y+ r! z7 `, P6 y* A

- m; e% h; _9 F0 M+ ~int solution(int A[], int N);
6 n; s" ^7 l: a8 E  ~- Y
# `7 p: k- V. w+ t
; ?9 \$ w6 A# f5 p  A* pthat, given a non-empty zero-indexed array A consisting of N integers, returns the maximum distance between indices of this array that have adjacent values. The function should return -1 if no adjacent indices exist.


For example, given array A such that:
) M+ O9 d' q* n& L4 e+ j
: W4 S0 a. e8 M
A[0] = 1
A[1] = 4
A[2] = 7
; w. [& k; G  H! e$ ~A[3] = 3
A[4] = 3
5 z. B+ X* m8 H$ o8 jA[5] = 5
  r0 z* T: _$ u. jthe function should return 4 because:
5 K% {3 O: Q5 x  h& \
8 P0 m& ^8 Z4 F* |* E+ N/ v/ ^
5 @* T6 s7 _, Z& Sindices 0 and 4 are adjacent because A[0] < A[4] and the array does not contain any value that lies strictly between A[0] = 1 and A[4] = 3;
the distance between these indices is abs(0 - 4) = 4;
9 W& \* \" I0 ~5 U7 ?, L( A2 cno other pair of adjacent indices that has a larger distance exists.
0 \' h+ f$ X% b, Y- \! cAssume that:

0 o- Q2 h2 V+ Z9 K$ k! b
N is an integer within the range [1..40,000];
0 g2 g& o) J# f$ Oeach element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
Complexity:

& H  H+ M; ~. N, [2 V8 Z
8 B" F7 q. s  I  U6 t" zexpected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
* h9 C2 E1 i; x7 l' a# w7 ^8 o

5 U. {* N7 {- P* }6 ]; A! ^4 `这个题的风格还是很不错的，有输入，输出，复杂度要求，数据范围……
题目也不难，如果把数重新排好顺序，那么选择的区间一定是数值上相邻的两个数（中间不能有别的数）。注意定义是整个数组没有它们之间的数，而不是P,Q下标之间……开始我把问题想难了，后来发现是简单题。 可以stable sort,也可以直接用index做sort，然后像去重那样选择每个数第一次和最后一次出现的位置，当然还可以用map记录每个数第一次和最后一次出现的位置，然后按key递增遍历map，其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。
" z1 U& w% Y5 o/ _
. a6 D+ O/ P$ s+ O- C& I
5 w$ X( }! J+ x  J$ B0 _- L

1. vector<int> b;
   
2. bool cmp(const int &x,const int &y) {
   , K8 F2 u& x5 x+ J0 T
3.         return b[x] < b[y];
   
4. }
   
5. 
   
6. int abs(int x) {
   
7.         return (x >= 0)?x:(-x);
   $ g0 J$ w; R! }$ S
8. }
   
9. 
   , K; Z) G2 R! e7 V$ y6 C) `
10. int cal(vector<int> &a) {
    
11. int n = a.size();
    
12. vector<int> ind(n);
    
13.         b = a;
    1 x+ @( r* F+ ^: f6 y# p' g
14.         for (int i = 0; i < n; ++i) {
    
15.                 ind【i】 = i;
    1 Q3 D+ c+ `6 {7 L: w  s
16.         }
    ! h- d/ \4 Y; |" |
17.         
    + Q) x& k9 D: u3 C8 D4 C
18.         sort(ind.begin(), ind.end(), cmp);
    ) f# z. ]  s! x; {3 e+ A' w' F
19.         int early, late, answer = -1;
    
20.         bool first = true;
    4 y, Z; k  h( ?1 j
21.         for (int i = 0; i < n; ) {
    0 `% w9 q0 x1 b% Y3 w3 [  k; k
22.                 int oldEarly = early, oldLate = late;
    
23.                 early = late = ind【i】;
    ' Y8 s! J: [2 i1 G7 a- H: l- ~
24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {
    $ u* u; u4 Z+ Y# w, V
25.                         early = min(early, ind【i】);
    / }' q/ e& E9 y) w
26.                         late = max(late, ind【i】);
    % r7 C: h% q5 V/ z: n
27.                 }
    
28.                 if (first) {
    " M5 w: D- N% {4 D' z: F- I. C
29.                         first = false;
    1 e1 Z% V+ p# p" |8 ?4 c
30.                 }
    & H1 y8 r/ k: t) m  l
31.                 else {
    
32.                         answer = max(answer, abs(early - oldEarly));
    , `, N8 R3 i+ v& |# k6 x
33.                         answer = max(answer, abs(early - oldLate));
    ; e) K" @" `* U0 c
34.                         answer = max(answer, abs(late - oldEarly));
    + d7 @8 s5 W# }* n2 P
35.                         answer = max(answer, abs(late- oldLate));
    ; p+ p5 X2 W, e% W/ `) i) _
36.                 }
    ! ~$ i6 j1 G) F
37.         }
    
38.         return answer;
    
39. }
    4 m4 ]: ~, F+ \4 m0 F1 D/ M- u

复制代码

5 M" I& ?; {" [3 F& Z! m

gjy14

大赞！！！！！！！！！

Ryan_Zhou

多谢分享 讲解非常详细