|
|
发表于 7-26-2016 10:23 PM
|
显示全部楼层
Java Solution with two hashmap recording largest and smallest index for each unique number
& d/ s; r3 x" B, ^, r) H: l- t9 W7 B9 U% o# L0 Q
int maximumDistanceBetweenIndices(int[] nums) {1 p) p- }/ S. s9 N5 H% Z
Map<Integer, Integer> num2SmallestIdx = new HashMap<>();
9 @# I Z" q6 j! U& \; R+ ~- \- B Map<Integer, Integer> num2BiggestIdx = new HashMap<>();! K, s& b* M' B
for(int i = 0; i< nums.length; i++) {
( D7 s x- o1 k* x) O num2SmallestIdx.put(nums【i】, Math.min(i, num2SmallestIdx.getOrDefault(nums【i】, Integer.MAX_VALUE)));8 T( C/ v; O/ j- p6 h' F% ~
num2BiggestIdx.put(nums【i】, Math.max(i, num2SmallestIdx.getOrDefault(nums【i】, Integer.MIN_VALUE)));' R- r, w% ]- t( Z1 K
}
' x* B! J4 O8 q9 s! _0 B$ l ; B% b6 I; Z: {
Arrays.sort(nums);
4 M; Q) L8 S: E4 t5 X; x$ f! `8 { int maxDistance = -1, lastBiggestIdx = Integer.MIN_VALUE, lastNum = Integer.MIN_VALUE;: W! c5 E! E ]5 O; X
for(int i = nums.length - 1; i >=0; i--) {
# b2 b. ~% {% _# h! ^ if (lastNum == nums【i】) continue;$ _7 h" C( w( |& q# ^1 C
lastNum = nums【i】;! T$ B a' ^2 q% Q% c% x
int smallestIdx = num2SmallestIdx.get(nums【i】);
1 z7 E, `( q/ [: w: Z+ z if (lastBiggestIdx >= 0) maxDistance = Math.max(maxDistance, Math.abs(lastBiggestIdx - smallestIdx));) ~2 b6 A' y9 t: F, T' D" Z1 U
lastBiggestIdx = num2BiggestIdx.get(nums【i】);
: h: o4 A$ A# c1 F* `: ] Y! H } 3 k6 |; f# D Y: z1 [
return maxDistance;
- _6 a; E6 T0 I6 \1 @$ Z }
8 H% F' L3 K) F5 J* m& j. q( b |
|
楼主: cpcs
发表于 2-15-2016 10:40 PM
