[理工] 演算法
各位大大好,第一次來這邊問問題,以後請多指教:>
Suppose that we are given a sequence of n unsorted values, say x1,x2,...,
xn, and at the same time, we are asked to qucikly answer repeated queries
defined as follows: Given i and j, where 1<=i<j<=n, find the smallest value
in xi, xi+1,....,xj.
(a) Please design a data structure that uses O(n^2) space and answers the
queries in O(1) time.
(b) Please design a data structure that uses O(n) space and answers the queries
in O(logn) time.
以上,求解,感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.237.64
※ 編輯: TokiyoHot 來自: 140.123.237.64 (11/13 23:11)
推
11/13 23:29, , 1F
11/13 23:29, 1F
→
11/13 23:33, , 2F
11/13 23:33, 2F
→
11/13 23:33, , 3F
11/13 23:33, 3F
推
11/14 00:34, , 4F
11/14 00:34, 4F
→
11/14 00:35, , 5F
11/14 00:35, 5F
→
11/16 23:24, , 6F
11/16 23:24, 6F
→
11/16 23:27, , 7F
11/16 23:27, 7F
討論串 (同標題文章)