w******n
发帖数: 61 | 1 Write a function that is given an array of integers. It should return true
if and only if there are two distinct indices i and j into the array such
that the difference between arr[i] and arr[j] is at most l and the
difference between i and j is at most k.
存在 O(n) 的解法么？我现在能想到的就是maintain一个 l 大小的sorted list 然后
一路扫过去。每次删头和加尾需要log l。然后判断新插入的数和相邻数是否满足 dif
< k。 就是O（n log l）。 |
h**d
发帖数: 630 | 2 Sorted可以做到O(n)
没sorted应该做不到
★ 发自iPhone App: ChineseWeb 7.8
【在 w******n 的大作中提到】
: Write a function that is given an array of integers. It should return true
: if and only if there are two distinct indices i and j into the array such
: that the difference between arr[i] and arr[j] is at most l and the
: difference between i and j is at most k.
: 存在 O(n) 的解法么？我现在能想到的就是maintain一个 l 大小的sorted list 然后
: 一路扫过去。每次删头和加尾需要log l。然后判断新插入的数和相邻数是否满足 dif
: < k。 就是O（n log l）。
|
i*********e
发帖数: 21 | 3 sliding window min/max.
if anyone window has max-min>l, then return false, else true. |
c******w
发帖数: 1108 | 4 public boolean findCloseNumbers(int[] A, int K, int L) {
Map map = new HashMap<>();
for (int i=0; i
if (i > K) map.remove(A[i-K-1]/L);
int key = A[i]/L;
if ( map.containsKey(key)
|| map.containsKey(key+1) && map.get(key+1) - A[i] <= L
|| map.containsKey(key-1) && A[i] - map.get(key-1) <= L )
return true;
map.put(key,A[i]);
}
return false;
} |
m********8
发帖数: 36 | 5 Nice solution!
我有个小问题， 当做key的时候，是不是应该对L+1做？
就是那个 int key = A[i]/(L+1) ?
谢谢。
【在 c******w 的大作中提到】
: public boolean findCloseNumbers(int[] A, int K, int L) {
: Map map = new HashMap<>();
: for (int i=0; i: if (i > K) map.remove(A[i-K-1]/L);
: int key = A[i]/L;
: if ( map.containsKey(key)
: || map.containsKey(key+1) && map.get(key+1) - A[i] <= L
: || map.containsKey(key-1) && A[i] - map.get(key-1) <= L )
: return true;
: map.put(key,A[i]);
|
c******w
发帖数: 1108 | 6 哦！好像是应该用L＋1做
【在 m********8 的大作中提到】
: Nice solution!
: 我有个小问题， 当做key的时候，是不是应该对L+1做？
: 就是那个 int key = A[i]/(L+1) ?
: 谢谢。
|
s******d
发帖数: 9806 | 7 why devided by L?
【在 c******w 的大作中提到】
: public boolean findCloseNumbers(int[] A, int K, int L) {
: Map map = new HashMap<>();
: for (int i=0; i: if (i > K) map.remove(A[i-K-1]/L);
: int key = A[i]/L;
: if ( map.containsKey(key)
: || map.containsKey(key+1) && map.get(key+1) - A[i] <= L
: || map.containsKey(key-1) && A[i] - map.get(key-1) <= L )
: return true;
: map.put(key,A[i]);
|
l*****n
发帖数: 246 | 8 好牛逼的解法！！！佩服
【在 c******w 的大作中提到】
: public boolean findCloseNumbers(int[] A, int K, int L) {
: Map map = new HashMap<>();
: for (int i=0; i: if (i > K) map.remove(A[i-K-1]/L);
: int key = A[i]/L;
: if ( map.containsKey(key)
: || map.containsKey(key+1) && map.get(key+1) - A[i] <= L
: || map.containsKey(key-1) && A[i] - map.get(key-1) <= L )
: return true;
: map.put(key,A[i]);
|
l*****n
发帖数: 246 | 9 好牛逼的解法！！！佩服
【在 c******w 的大作中提到】
: public boolean findCloseNumbers(int[] A, int K, int L) {
: Map map = new HashMap<>();
: for (int i=0; i: if (i > K) map.remove(A[i-K-1]/L);
: int key = A[i]/L;
: if ( map.containsKey(key)
: || map.containsKey(key+1) && map.get(key+1) - A[i] <= L
: || map.containsKey(key-1) && A[i] - map.get(key-1) <= L )
: return true;
: map.put(key,A[i]);
|
