为什么正规经销商的配件这么贵？# PhotoGear - 摄影器材
g*c
1 楼
设计一个数据结构，储存一个数组，支持update任意一个值，支持查询数组的min。
我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。
我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。
a*a
2 楼
在42nd street photo上看K-5的配件，为什么都比amazon和ebay上贵呢？比如说电池和
充电器。质量会有很大的不同么？
充电器。质量会有很大的不同么？
d*l
3 楼
不是heap么
b*6
4 楼
人就指这个赚钱的
bestbuy里的hdmi cable 50块一根
bestbuy里的hdmi cable 50块一根
g*c
5 楼
heap如何update任意member？
【在 d***l 的大作中提到】
: 不是heap么
【在 d***l 的大作中提到】
: 不是heap么
S*x
6 楼
正经经销商的啥都贵
f*n
7 楼
和segment tree没关系，C++的set和Java的TreeSet都可以解决
update是logN，查询min是1
heap也可以，时间复杂度一样
【在 g*c 的大作中提到】
: 设计一个数据结构，储存一个数组，支持update任意一个值，支持查询数组的min。
: 我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。
update是logN，查询min是1
heap也可以，时间复杂度一样
【在 g*c 的大作中提到】
: 设计一个数据结构，储存一个数组，支持update任意一个值，支持查询数组的min。
: 我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。
f*n
8 楼
修改这个member的值
如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
其他，不用处理
【在 g*c 的大作中提到】
: heap如何update任意member？
如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
其他，不用处理
【在 g*c 的大作中提到】
: heap如何update任意member？
g*c
9 楼
如果是key value pair，update value呢？
【在 f*******n 的大作中提到】
: 和segment tree没关系，C++的set和Java的TreeSet都可以解决
: update是logN，查询min是1
: heap也可以，时间复杂度一样
【在 f*******n 的大作中提到】
: 和segment tree没关系，C++的set和Java的TreeSet都可以解决
: update是logN，查询min是1
: heap也可以，时间复杂度一样
g*c
10 楼
heap如何constant time或者logN time找到任意member？
【在 f*******n 的大作中提到】
: 修改这个member的值
: 如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
: 如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
: 其他，不用处理
【在 f*******n 的大作中提到】
: 修改这个member的值
: 如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
: 如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
: 其他，不用处理
g*c
11 楼
我想了一下，可以用multimap，value => key，但这样update的worst case是O(N)
【在 g*c 的大作中提到】
: 如果是key value pair，update value呢？
【在 g*c 的大作中提到】
: 如果是key value pair，update value呢？
r*r
12 楼
更正：
每次更新时，将最值也更新。
// Query of min time: O(1)
public int getMin() { return this.min; }
============================
抛砖引玉，欢迎批评，期待更好的解法。
采用TreeMap，使用数组的值作key，同一值可能有重复，对应的indices组成的HashSet
作value。
更新：O(logn)，查询最值：O(logn)。
import java.util.*;
class AccessMinAndUpdateOfArray {
private int min = Integer.MAX_VALUE;
private int[] a;
private TreeMap> tm;
// Initialization time: O(nlogn).
public AccessMinAndUpdateOfArray(int[] a) {
this.a = a;
tm = new TreeMap<>();
for (int i = 0; i < a.length; i) {
this.min = Math.min(a[i], this.min);
tm.computeIfAbsent(a[i], s -> new HashSet<>()).add(i);
}
}
// Query of min time: O(logn).
public int getMin() { return tm.firstEntry().getKey(); }
// Update time: O(logn).
public void update(int id, int val) { // update a[id] with val.
if (val == a[id]) { return; } // same value, nothing to do.
// remove old value - 2 cases: multiple/one
// element(s) with value of a[id] in a.
if (tm.get(a[id]).size() > 1) { tm.get(a[id]).remove(id); }
else { tm.remove(a[id]); } // only 1 value of a[id] in a.
// add new value.
tm.computeIfAbsent(val, s -> new HashSet<>()).add(id);
this.a[id] = val;
this.min = Math.min(val, this.min);
}
}
每次更新时，将最值也更新。
// Query of min time: O(1)
public int getMin() { return this.min; }
============================
抛砖引玉，欢迎批评，期待更好的解法。
采用TreeMap，使用数组的值作key，同一值可能有重复，对应的indices组成的HashSet
作value。
更新：O(logn)，查询最值：O(logn)。
import java.util.*;
class AccessMinAndUpdateOfArray {
private int min = Integer.MAX_VALUE;
private int[] a;
private TreeMap
// Initialization time: O(nlogn).
public AccessMinAndUpdateOfArray(int[] a) {
this.a = a;
tm = new TreeMap<>();
for (int i = 0; i < a.length; i) {
this.min = Math.min(a[i], this.min);
tm.computeIfAbsent(a[i], s -> new HashSet<>()).add(i);
}
}
// Query of min time: O(logn).
public int getMin() { return tm.firstEntry().getKey(); }
// Update time: O(logn).
public void update(int id, int val) { // update a[id] with val.
if (val == a[id]) { return; } // same value, nothing to do.
// remove old value - 2 cases: multiple/one
// element(s) with value of a[id] in a.
if (tm.get(a[id]).size() > 1) { tm.get(a[id]).remove(id); }
else { tm.remove(a[id]); } // only 1 value of a[id] in a.
// add new value.
tm.computeIfAbsent(val, s -> new HashSet<>()).add(id);
this.a[id] = val;
this.min = Math.min(val, this.min);
}
}
a*u
13 楼
getFirstEntry() 为什么是O(1)不是O(logn)
【在 r********r 的大作中提到】
: 更正：
: 每次更新时，将最值也更新。
: // Query of min time: O(1)
: public int getMin() { return this.min; }
: ============================
: 抛砖引玉，欢迎批评，期待更好的解法。
: 采用TreeMap，使用数组的值作key，同一值可能有重复，对应的indices组成的HashSet
: 作value。
: 更新：O(logn)，查询最值：O(logn)。
: import java.util.*;
【在 r********r 的大作中提到】
: 更正：
: 每次更新时，将最值也更新。
: // Query of min time: O(1)
: public int getMin() { return this.min; }
: ============================
: 抛砖引玉，欢迎批评，期待更好的解法。
: 采用TreeMap，使用数组的值作key，同一值可能有重复，对应的indices组成的HashSet
: 作value。
: 更新：O(logn)，查询最值：O(logn)。
: import java.util.*;
r*r
14 楼
Thanks for correction, I appreciate it and update the O(1) to O(logn).
【在 a******u 的大作中提到】
: getFirstEntry() 为什么是O(1)不是O(logn)
【在 a******u 的大作中提到】
: getFirstEntry() 为什么是O(1)不是O(logn)
f*n
15 楼
我写的是修改，是已知位置的情况下
如果你要查找，那就别用heap，直接用set
【在 g*c 的大作中提到】
: heap如何constant time或者logN time找到任意member？
如果你要查找，那就别用heap，直接用set
【在 g*c 的大作中提到】
: heap如何constant time或者logN time找到任意member？
f*n
16 楼
unordered_map
and
multiset
【在 g*c 的大作中提到】
: 如果是key value pair，update value呢？
and
multiset
【在 g*c 的大作中提到】
: 如果是key value pair，update value呢？
a*a
17 楼
感觉上面的都偏复杂了一点，如果查询是某个位置范围内的min value，估计就得用
segment tree了。
这个不需要的话，就用原来数组 data和一个multiset s就可以了，
// O(logN)
update(pos, val):
s.erase(s.find(data[pos]))
s.insert(val)
data[pos] = val
// O(1)
min():
return *s.rbegin()
segment tree了。
这个不需要的话，就用原来数组 data和一个multiset s就可以了，
// O(logN)
update(pos, val):
s.erase(s.find(data[pos]))
s.insert(val)
data[pos] = val
// O(1)
min():
return *s.rbegin()
d*l
18 楼
可以用一个map存key->updated/post-heapify index
[在 gtc (牛顿的苹果) 的大作中提到：]
:如果是key value pair，update value呢？
[在 gtc (牛顿的苹果) 的大作中提到：]
:如果是key value pair，update value呢？
M*6
19 楼
最简单的办法：用一个数组存Array，再加一个变量（比如数组的最后一位）存Min的
index不就行了吗？每次更
新值得时候比较一下是否小于min。
这样复杂度是： 更新 O(1), GetMin() 也是O(1).
满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。
index不就行了吗？每次更
新值得时候比较一下是否小于min。
这样复杂度是： 更新 O(1), GetMin() 也是O(1).
满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。
M*6
20 楼
堆会把最小值之外的元素也基本排序，这里只要最小值，用堆就是浪费时间。
Segment Tree就是二分查找任意元素的思想，对于只找最小值，也是over kill。
Segment Tree就是二分查找任意元素的思想，对于只找最小值，也是over kill。
r*e
21 楼
数组更新如何做到O(1)?
数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？
【在 M***6 的大作中提到】
: 最简单的办法：用一个数组存Array，再加一个变量（比如数组的最后一位）存Min的
: index不就行了吗？每次更
: 新值得时候比较一下是否小于min。
: 这样复杂度是： 更新 O(1), GetMin() 也是O(1).
: 满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。
数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？
【在 M***6 的大作中提到】
: 最简单的办法：用一个数组存Array，再加一个变量（比如数组的最后一位）存Min的
: index不就行了吗？每次更
: 新值得时候比较一下是否小于min。
: 这样复杂度是： 更新 O(1), GetMin() 也是O(1).
: 满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。
l*p
22 楼
如果是我，我会先问他，你的应用场景是什么，update 多还是min_query多？
上来就找最优，呵呵
上来就找最优，呵呵
s*g
23 楼
首先你这是有序组
其次更新以后可能扰乱原来的顺序，例如把最小值更新成一个超大数，如果是array不
是linkedlist的话需要移位会O(N)
然后你的data[pos]也得更新
【在 a*****a 的大作中提到】
: 感觉上面的都偏复杂了一点，如果查询是某个位置范围内的min value，估计就得用
: segment tree了。
: 这个不需要的话，就用原来数组 data和一个multiset s就可以了，
: // O(logN)
: update(pos, val):
: s.erase(s.find(data[pos]))
: s.insert(val)
: data[pos] = val
: // O(1)
: min():
其次更新以后可能扰乱原来的顺序，例如把最小值更新成一个超大数，如果是array不
是linkedlist的话需要移位会O(N)
然后你的data[pos]也得更新
【在 a*****a 的大作中提到】
: 感觉上面的都偏复杂了一点，如果查询是某个位置范围内的min value，估计就得用
: segment tree了。
: 这个不需要的话，就用原来数组 data和一个multiset s就可以了，
: // O(logN)
: update(pos, val):
: s.erase(s.find(data[pos]))
: s.insert(val)
: data[pos] = val
: // O(1)
: min():
M*6
24 楼
我的理解是更新值就是指的是更新某个index对应的值，因为题中提到了数组。我不觉
得是有一堆数2，3，5，然后让你把3变成9，真这样的话，用一个hashset/hashmap不就
可以了吗
【在 r**********e 的大作中提到】
: 数组更新如何做到O(1)?
: 数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？
得是有一堆数2，3，5，然后让你把3变成9，真这样的话，用一个hashset/hashmap不就
可以了吗
【在 r**********e 的大作中提到】
: 数组更新如何做到O(1)?
: 数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？
M*6
25 楼
同感。需要跟面试官double check。当前题的描述，根本就用不上堆，segment tree之
类的
【在 l***p 的大作中提到】
: 如果是我，我会先问他，你的应用场景是什么，update 多还是min_query多？
: 上来就找最优，呵呵
类的
【在 l***p 的大作中提到】
: 如果是我，我会先问他，你的应用场景是什么，update 多还是min_query多？
: 上来就找最优，呵呵
相关阅读
70-200/4 IS是狗头么？有什么配件给Pen1 LCD遮光的吗？Contax也有了一个革命机。。。330474141842Sigma 50-200mm f/4.0-5.6 DC IF SLD OS Lens $159 at Amazonx1是咋整边角的？Canon S95还是Panasonic lx3俺也革命了带三个模特拍外景，如何协调？完美的革命机终于出现，富士X100发布，旁轴的遗老遗少可以上了这个TrekPod怎么样Rebel xt故障大马兔，大马三和小马四的45点对焦是同样的产品吗？K5最应该加上一个功能视频的话是不是NEX 5 > A55?大牛能说说胶片的色彩的奇妙之处么？万佛，请推荐light room教程算了下，摄影师赚不了多少钱阿难道佳能要完蛋了?35mm 视角还行。