双黄包求hd moving coupon code - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

双黄包求hd moving coupon code

双黄包求hd moving coupon code# Living

p*22011-08-01 07:08

1 楼

public void Add(Task task)
{
int i=0;
for(;i{
if(task.deadline{
list.Insert(i,task);
break;
}
}
if(i==list.Count)
list.Add(task);
}
public void Add(Task task)
{
if (list.Count == 0)
{
list.Add(task);
return;
}
int start = 0;
int end = list.Count - 1;
while (start <= end)
{
if (start == end)
{
if (list[start].deadline > task.deadline)
list.Insert(start, task);
else
list.Insert(start + 1, task);
return;
}
int mid = (start + end) / 2;
if (list[mid].deadline == task.deadline)
{
list.Insert(mid, task);
return;
}
if (list[mid].deadline < task.deadline)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
}
}

x*m2011-08-01 07:08

2 楼

c*e2011-08-01 07:08

3 楼

How do you know it is slower than linear? Is your n large enough?

q*x2011-08-01 07:08

4 楼

你的二分法罗嗦。

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

: public void Add(Task task)
: {
: int i=0;
: for(;i: {
: if(task.deadline: {
: list.Insert(i,task);
: break;
: }

L*R2011-08-01 07:08

5 楼

N不够大吧

p*22011-08-01 07:08

6 楼

我做一道题，linear能pass 50%的test case， binary 只能过10%。虽然写的罗嗦，但
是还是很奇怪为什么这样子。
我后来从后往前linear search, 还是这个结果。

f*t2011-08-01 07:08

7 楼

你这个是java的arraylist?
insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
。

q*x2011-08-01 07:08

8 楼

不是list吗？

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

: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。

r*t2011-08-01 07:08

9 楼

arraylist 有 random access 吗？insert 该没有关系，两个办法最后都是 insert 一次。
话说你这个 binary search 有私货，找到以后 return iterator 好了，为啥要 insert 呢？

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

: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。

f*t2011-08-01 07:08

10 楼

list不能random access

【在 q****x 的大作中提到】

: 不是list吗？

q*x2011-08-01 07:08

11 楼

good catch, thx.

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

: list不能random access

p*22011-08-01 07:08

12 楼

一次。
insert 呢？
return iterator什么意思呀？我insert是因为下次还需要用。

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

: arraylist 有 random access 吗？insert 该没有关系，两个办法最后都是 insert 一次。
: 话说你这个 binary search 有私货，找到以后 return iterator 好了，为啥要 insert 呢？

q*x2011-08-01 07:08

13 楼

你算法有问题。
如果是数组，插入是线性的。
如果是链表，二分查找不行。

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

:
: 一次。
: insert 呢？
: return iterator什么意思呀？我insert是因为下次还需要用。

r*t2011-08-01 07:08

14 楼

只 pass 部分估计是边界条件没搞对。自己能搞点 test case 么？

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

: 我做一道题，linear能pass 50%的test case， binary 只能过10%。虽然写的罗嗦，但
: 是还是很奇怪为什么这样子。
: 我后来从后往前linear search, 还是这个结果。

r*t2011-08-01 07:08

15 楼

c++ 里面 search 都返回 iterator/pointer, 以为 java 应该更自然点。。。

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

:
: 一次。
: insert 呢？
: return iterator什么意思呀？我insert是因为下次还需要用。

q*x2011-08-01 07:08

16 楼

bool std::binary_search()

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

: c++ 里面 search 都返回 iterator/pointer, 以为 java 应该更自然点。。。

p*22011-08-01 07:08

17 楼

相当于java 的 arraylist, 关键是两种算法都有insert呀。

【在 q****x 的大作中提到】

: 你算法有问题。
: 如果是数组，插入是线性的。
: 如果是链表，二分查找不行。

q*x2011-08-01 07:08

18 楼

你怎么知道慢？

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

:
: 相当于java 的 arraylist, 关键是两种算法都有insert呀。

p*22011-08-01 07:08

19 楼

test case 运行到50%超时， binary运行到10%就超时了。很奇怪。

【在 q****x 的大作中提到】

: 你怎么知道慢？

r*t2011-08-01 07:08

20 楼

okay, 原来只要返回 true/false 就行了。

【在 q****x 的大作中提到】

: bool std::binary_search()

x*22011-08-01 07:08

21 楼

同意这个观点。
楼主不妨注释掉insert操作再跑一次

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

: 你这个是java的arraylist?
: insert操作是O(n)+各种memory copy的吧，相比之下查找的复杂度已经影响不大了。。
: 。

a*p2011-08-01 07:08

22 楼

同意楼上说的。search是重点。写了点玩玩，看看对不对。
public class Test {
Task[] list;
int search(Task task) {
int i = 0;
do {
if (task.deadline <= list[i].deadline) {
return i;
}
} while (++i < list.length);
return list.length-1;
}
int binarySearch(Task task) {
int i = list.length;
int k = 0;
int j;
do {

if ((i+1 + k) % 2 != 0){
j = (i+k)/2;
} else{
j = (i+1 + k)/2;
}

if (j == i) {
if (task.deadline >= list[i-1].deadline) {
return i-1;
} else {
return i;
}
} else {
if (task.deadline >= list[j].deadline) {
k = j;
} else {
i = j;
j = 0;
}
}

} while (j < i);
return j;
}
public static void main(String[] args) {
int size = 5*1000*1000;
Test test = new Test();
test.list = new Task[size];
Task task;
for (int i = 0; i < size; i++) {
task = new Task(i);
test.list[i] = task;
}
Task t = new Task((int) (Math.random() * size));
System.out.println("list size:"+size+"; deadline:"+t.deadline);
long time = System.currentTimeMillis();
System.out.println("index: " + test.search(t));
System.out.println(System.currentTimeMillis() - time);
time = System.currentTimeMillis();
System.out.println("index: " + test.binarySearch(t));
System.out.println(System.currentTimeMillis() - time);
}
}
class Task {
int deadline;
Task(int i){
deadline = i;
}
}