|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑 3 @: Q$ t! H7 l3 ]1 v6 T
0 ?+ _, F, |( @+ T
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。
+ s; _ [6 Y1 ]) N! E: i7 R5 } l# I' A: G
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 ^2 U' e5 G3 C y: g/ ~1 q4 W6 q
& Y8 J8 U6 z v8 f, E
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( s! z7 `: Y2 U' W n& P/ T" o: l* k
A* v8 V! M* ~7 i- O2 ^. i( RFor example, in array A such that: / x b4 n* u% G7 w
A[0] = 0
: @' f9 x- W3 e( C/ o1 s) k EA[1] = 3 , ^; h3 Q8 O$ x9 U: ~/ S
A[2] = 3 " v5 i3 t& Z- y! [! }2 u* I. b6 P0 z& [
A[3] = 7
7 W5 V* G' I! CA[4] = 5
! O8 p! J! |, B" u: k$ `3 o) h2 }A[5] = 3 ; f/ \3 o" T5 D. z2 x2 @
A[6] = 11
5 h/ A1 E% W" o4 A4 s0 c9 \: r+ ?. ]A[7] = 1 / j2 v* K9 }1 p$ ~1 x6 b
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), " o% ?0 r7 Q' O+ S
(3, 6), (4, 5), (5, 7). ( q. U3 f; [9 K; ]
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. ; U' z# j/ N' P c3 ^
$ N1 H/ k2 e7 e8 A) q9 t0 q {- E
5 N; s. Z w4 L- |" U9 B
Write a function:
6 M8 I7 K. L- ~9 D L
$ w' X& x! ~: l, b+ R. X3 i' k/ y' D2 f
int solution(int A[], int N);
& w- W% W0 C* E. \9 v- J- K4 h E2 C5 N0 z+ ]
# x' M) W5 i) A( {- Q, U9 s
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. 6 T4 m( u$ j, t- J6 f5 M
) M8 O0 S3 h& c |
' w; ~) ~6 ?% Z; t1 r/ j& c- \8 KFor example, given array A such that: - c; F8 e! r* Z0 R& w# p
' \' _/ q( k* v2 O2 [
3 j+ _8 Y* y# L% V; v3 r/ e! SA[0] = 1 ; J4 R) h6 r, h/ r. p
A[1] = 4
- F' ^" R) ^7 v' [2 r6 l% G- `; eA[2] = 7 , M1 Y$ U" ~: k6 J6 D8 z
A[3] = 3 ; D5 W/ j& E s3 r7 }* W
A[4] = 3 & T5 h& i7 \* z% g+ r! Q- o
A[5] = 5 ?. Z3 y4 f3 v/ L% U/ U8 X3 s7 y
the function should return 4 because: & r* f4 m. b# g9 T
( D0 T2 U' ]4 K. t* S( f7 b7 `. ~) C5 d s1 C) e1 C( c2 s
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: ' N2 H! d# F/ |% Y7 n
) y* f4 E1 |2 A/ C& T
6 I( c" y9 i- L& J
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: 1 O" Y u3 E" m* H v8 c
% L3 C( C) V* `% {* t
! 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). # i( u" \* G- i' Q
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的和它给的不同。+ v* b! n; U4 ^. s) k9 f+ F8 }
, k# W' X4 i# r2 F5 F
5 c$ f1 e+ v$ P s% O2 J. O8 c- vector<int> b;# x+ o4 O' j9 v. Z: p. u
- bool cmp(const int &x,const int &y) {
- J1 |, F) E7 v - return b[x] < b[y];
- I: ]7 u" o% T( [- E$ l" ` - }
" n3 {' Q3 s$ e4 K' H0 F4 n0 B - $ n4 B3 i$ P$ V6 ~
- int abs(int x) {. ^3 N6 D0 x' Y7 A0 U' Q# x' W
- return (x >= 0)?x:(-x);. j% M8 A- r: [9 f; s
- }" z/ }3 B+ s# d* N1 Z9 Q1 I3 d' b
- 6 Q1 C: h9 j; r
- int cal(vector<int> &a) {
, q" N R0 l7 ]9 S9 g6 M - int n = a.size();7 z K8 T' x' a5 h) s
- vector<int> ind(n);
y- W: m |, q7 z; u3 C7 ~ - b = a;6 n; K. k. Q- i3 f
- for (int i = 0; i < n; ++i) {
- m+ z; P$ d! j% ]; E - ind【i】 = i;
" X3 ^- F; J9 F" p2 z2 @: q* H I - }! V% h- {$ v( _4 M: W: v
- 2 o. X$ M# I' n; E/ X& j
- sort(ind.begin(), ind.end(), cmp);$ C: U2 j* m c( g- ^
- int early, late, answer = -1;* F& J4 u. u* \( [
- bool first = true; W) @! H' v% y9 y
- for (int i = 0; i < n; ) {
5 F! n+ S! Y# z6 \1 e - int oldEarly = early, oldLate = late;' G& B8 _/ p7 j9 @" s8 F8 \' \
- early = late = ind【i】;
) U$ A. X# }0 m5 N1 [9 K - for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {
! o' F4 x8 w' G& P# z5 N$ | - early = min(early, ind【i】);4 U, j0 B; O! P5 n
- late = max(late, ind【i】);
$ @9 n1 F2 Q {) b j2 h2 o - }
+ R0 ^- N0 P/ Z; Z& B! n6 v - if (first) {
4 Z7 I: W9 O- o7 n$ `0 y; S - first = false;' ~/ ^" v3 ?5 W2 a( }
- }
! w. `" }; A4 i! B - else {
9 r2 ?3 M# ]- V - answer = max(answer, abs(early - oldEarly));
4 o8 O. {; X7 L" N5 w# l - answer = max(answer, abs(early - oldLate));! C: v6 {- [9 B) H8 m& Q+ w' H$ Y% V; R
- answer = max(answer, abs(late - oldEarly));# R& w" P7 U4 Y2 u1 \
- answer = max(answer, abs(late- oldLate));; E- I& u: Q/ z" r
- }9 U5 S0 [7 Y* \2 J& l# j" u; T$ L
- }
" t2 u7 ~$ g C' u* b1 O - return answer;
9 z. E( R1 R# L O) [8 J - }
4 M) w v7 Q! R4 B4 g X0 s# s
复制代码
, ~ M6 L1 a! x9 z7 f9 y+ @4 ]3 r; e3 P z
* K, y! M& a6 ^2 C2 n y+ ^! a& f- O4 [ q1 c$ B2 t
* i( L9 K; m, B5 x |0 w }: q6 u
- @' { |8 J, L* z. U) r2 P
|
|