面经上一个题及解法

cpcs

刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。
+ s; _  [6 Y1 ]) N

  B' F' f" I! U! Y$ t1 eInteger V lies strictly between integers U and W if U < V < W or if U > V > W.
( O% b$ I8 @0 s! t3 x! i0 ^

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].
  R" L/ P* q2 J6 |& `0 a, z

  A* v8 V! M* ~7 i- O2 ^. i( RFor example, in array A such that:
A[0] = 0
: @' f9 x- W3 e( C/ o1 s) k  EA[1] = 3
A[2] = 3
A[3] = 7
7 W5 V* G' I! CA[4] = 5
! O8 p! J! |, B" u: k$ `3 o) h2 }A[5] = 3
A[6] = 11
5 h/ A1 E% W" o4 A4 s0 c9 \: r+ ?. ]A[7] = 1
the following pairs of indices have adjacent values:
( H7 f4 V6 j1 G% U6 b; }
/ n% p* d6 |# c( C* E" e, \9 [
; l3 ^; D5 P) j9 d(0, 7), (1, 4), (1, 7),
  J8 M; ]6 C" t: I* N9 i2 G# a$ K(2, 4), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
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.
4 ~7 i/ r+ S! h! n8 I2 |" o
! g$ v& d8 r/ X# u
2 W: N. t- I4 n: @3 Y+ U) c4 r2 EGiven 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.


Write a function:
6 M8 I7 K. L- ~9 D  L
$ w' X& x! ~: l, b+ R
int solution(int A[], int N);
& w- W% W0 C* E. \9 v- J- K

that, 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.


' w; ~) ~6 ?% Z; t1 r/ j& c- \8 KFor example, given array A such that:


3 j+ _8 Y* y# L% V; v3 r/ e! SA[0] = 1
A[1] = 4
- F' ^" R) ^7 v' [2 r6 l% G- `; eA[2] = 7
A[3] = 3
A[4] = 3
A[5] = 5
the function should return 4 because:

( D0 T2 U' ]4 K. t* S( f7 b
indices 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;
' L  L$ {9 J, }* @the distance between these indices is abs(0 - 4) = 4;
4 n% e, a/ [7 \! x1 @* r" D! Ino other pair of adjacent indices that has a larger distance exists.
) ?" M4 ^+ R/ o6 m7 p# WAssume that:


N is an integer within the range [1..40,000];
; V0 ?6 n4 v/ ?6 k  d& W; ]# R' Heach element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
5 C+ {0 |4 a+ PComplexity:


! s( t0 g8 Z* dexpected worst-case time complexity is O(N*log(N));
/ j& W& F. n  zexpected 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.
+ {3 F- t4 V- e7 g4 ~1 H, p
5 ?* Q$ |: e. G1 G; S4 K
9 d; Z  f/ G: b6 h  d这个题的风格还是很不错的，有输入，输出，复杂度要求，数据范围……
) S) a2 p' r: d1 e) u4 u题目也不难，如果把数重新排好顺序，那么选择的区间一定是数值上相邻的两个数（中间不能有别的数）。注意定义是整个数组没有它们之间的数，而不是P,Q下标之间……开始我把问题想难了，后来发现是简单题。 可以stable sort,也可以直接用index做sort，然后像去重那样选择每个数第一次和最后一次出现的位置，当然还可以用map记录每个数第一次和最后一次出现的位置，然后按key递增遍历map，其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。


5 c$ f1 e+ v$ P  s% O2 J. O8 c

1. vector<int> b;
   
2. bool cmp(const int &x,const int &y) {
   - J1 |, F) E7 v
3.         return b[x] < b[y];
   - I: ]7 u" o% T( [- E$ l" `
4. }
   " n3 {' Q3 s$ e4 K' H0 F4 n0 B
5. 
   
6. int abs(int x) {
   
7.         return (x >= 0)?x:(-x);
   
8. }
   
9. 
   
10. int cal(vector<int> &a) {
    , q" N  R0 l7 ]9 S9 g6 M
11. int n = a.size();
    
12. vector<int> ind(n);
      y- W: m  |, q7 z; u3 C7 ~
13.         b = a;
    
14.         for (int i = 0; i < n; ++i) {
    - m+ z; P$ d! j% ]; E
15.                 ind【i】 = i;
    " X3 ^- F; J9 F" p2 z2 @: q* H  I
16.         }
    
17.         
    
18.         sort(ind.begin(), ind.end(), cmp);
    
19.         int early, late, answer = -1;
    
20.         bool first = true;
    
21.         for (int i = 0; i < n; ) {
    5 F! n+ S! Y# z6 \1 e
22.                 int oldEarly = early, oldLate = late;
    
23.                 early = late = ind【i】;
    ) U$ A. X# }0 m5 N1 [9 K
24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {
    ! o' F4 x8 w' G& P# z5 N$ |
25.                         early = min(early, ind【i】);
    
26.                         late = max(late, ind【i】);
    $ @9 n1 F2 Q  {) b  j2 h2 o
27.                 }
    + R0 ^- N0 P/ Z; Z& B! n6 v
28.                 if (first) {
    4 Z7 I: W9 O- o7 n$ `0 y; S
29.                         first = false;
    
30.                 }
    ! w. `" }; A4 i! B
31.                 else {
    9 r2 ?3 M# ]- V
32.                         answer = max(answer, abs(early - oldEarly));
    4 o8 O. {; X7 L" N5 w# l
33.                         answer = max(answer, abs(early - oldLate));
    
34.                         answer = max(answer, abs(late - oldEarly));
    
35.                         answer = max(answer, abs(late- oldLate));
    
36.                 }
    
37.         }
    " t2 u7 ~$ g  C' u* b1 O
38.         return answer;
    9 z. E( R1 R# L  O) [8 J
39. }
    4 M) w  v7 Q! R4 B4 g  X0 s# s

复制代码

, ~  M6 L1 a! x9 z

* K, y! M& a6 ^2 C2 n

gjy14

大赞！！！！！！！！！

Ryan_Zhou

多谢分享 讲解非常详细