为什么正规经销商的配件这么贵？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

为什么正规经销商的配件这么贵？

为什么正规经销商的配件这么贵？# PhotoGear - 摄影器材

g*c2011-10-29 07:10

1 楼

设计一个数据结构，储存一个数组，支持update任意一个值，支持查询数组的min。
我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。

a*a2011-10-29 07:10

2 楼

在42nd street photo上看K-5的配件，为什么都比amazon和ebay上贵呢？比如说电池和
充电器。质量会有很大的不同么？

d*l2011-10-29 07:10

3 楼

不是heap么

b*62011-10-29 07:10

4 楼

人就指这个赚钱的
bestbuy里的hdmi cable 50块一根

g*c2011-10-29 07:10

5 楼

heap如何update任意member？

【在 d***l 的大作中提到】

: 不是heap么

S*x2011-10-29 07:10

6 楼

正经经销商的啥都贵

f*n2011-10-29 07:10

7 楼

和segment tree没关系，C++的set和Java的TreeSet都可以解决
update是logN，查询min是1
heap也可以，时间复杂度一样

【在 g*c 的大作中提到】

: 设计一个数据结构，储存一个数组，支持update任意一个值，支持查询数组的min。
: 我理解是segment tree的题，两个操作都可以做到logN。不知道理解的对不对。

f*n2011-10-29 07:10

8 楼

修改这个member的值
如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
其他，不用处理

【在 g*c 的大作中提到】

: heap如何update任意member？

g*c2011-10-29 07:10

9 楼

如果是key value pair，update value呢？

【在 f*******n 的大作中提到】

: 和segment tree没关系，C++的set和Java的TreeSet都可以解决
: update是logN，查询min是1
: heap也可以，时间复杂度一样

g*c2011-10-29 07:10

10 楼

heap如何constant time或者logN time找到任意member？

【在 f*******n 的大作中提到】

: 修改这个member的值
: 如果是变小且小于父节点，swap这个节点和父节点，然后递归处理父节点
: 如果是变大并且大于一个子节点，swap这个节点和偏小的子节点，然后递归处理
: 其他，不用处理

g*c2011-10-29 07:10

11 楼

我想了一下，可以用multimap，value => key，但这样update的worst case是O(N)

【在 g*c 的大作中提到】

: 如果是key value pair，update value呢？

r*r2011-10-29 07:10

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);
}
}

a*u2011-10-29 07:10

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*r2011-10-29 07:10

14 楼

Thanks for correction, I appreciate it and update the O(1) to O(logn).

【在 a******u 的大作中提到】

: getFirstEntry() 为什么是O(1)不是O(logn)

f*n2011-10-29 07:10

15 楼

我写的是修改，是已知位置的情况下
如果你要查找，那就别用heap，直接用set

【在 g*c 的大作中提到】

: heap如何constant time或者logN time找到任意member？

f*n2011-10-29 07:10

16 楼

unordered_map
and
multiset

【在 g*c 的大作中提到】

: 如果是key value pair，update value呢？

a*a2011-10-29 07:10

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()

d*l2011-10-29 07:10

18 楼

可以用一个map存key->updated/post-heapify index
[在 gtc (牛顿的苹果) 的大作中提到：]
:如果是key value pair，update value呢？

M*62011-10-29 07:10

19 楼

最简单的办法：用一个数组存Array，再加一个变量（比如数组的最后一位）存Min的
index不就行了吗？每次更
新值得时候比较一下是否小于min。
这样复杂度是：更新 O(1), GetMin() 也是O(1).
满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。

M*62011-10-29 07:10

20 楼

堆会把最小值之外的元素也基本排序，这里只要最小值，用堆就是浪费时间。
Segment Tree就是二分查找任意元素的思想，对于只找最小值，也是over kill。

r*e2011-10-29 07:10

21 楼

数组更新如何做到O(1)?
数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？

【在 M***6 的大作中提到】

: 最简单的办法：用一个数组存Array，再加一个变量（比如数组的最后一位）存Min的
: index不就行了吗？每次更
: 新值得时候比较一下是否小于min。
: 这样复杂度是：更新 O(1), GetMin() 也是O(1).
: 满足要求不？大家是不是刷题刷出固定思维了，还是我对题意哪里理解不对。

l*p2011-10-29 07:10

22 楼

如果是我，我会先问他，你的应用场景是什么，update 多还是min_query多？
上来就找最优，呵呵

s*g2011-10-29 07:10

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():

M*62011-10-29 07:10

24 楼

我的理解是更新值就是指的是更新某个index对应的值，因为题中提到了数组。我不觉
得是有一堆数2，3，5，然后让你把3变成9，真这样的话，用一个hashset/hashmap不就
可以了吗

【在 r**********e 的大作中提到】

: 数组更新如何做到O(1)?
: 数组的index就是数值吗，不是的话如何更新需要更新的数值并做到O(1)？

M*62011-10-29 07:10

25 楼

同感。需要跟面试官double check。当前题的描述，根本就用不上堆，segment tree之
类的

【在 l***p 的大作中提到】

: 如果是我，我会先问他，你的应用场景是什么，update 多还是min_query多？
: 上来就找最优，呵呵