Redian新闻
>
Berkin N300 的F7D7301 与 F7D7302 有什么不同?
avatar
Berkin N300 的F7D7301 与 F7D7302 有什么不同?# Hardware - 计算机硬件
v*a
1
Given an array of n elements and an integer k where kElements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
algorithm to sort in O(n) time and O(1) space.
怎么做这个?
avatar
e*y
2
EB2,LD主申请人,我要什么时候可以拿到EAD?是不是485交上去后,我就可以申请EAD
了?一般要多久可以批下来?
avatar
a*e
3
爱扣,亲家, 这歌你一点我就开始学了,一直学到今天,唱了好多遍才完成的。
金志文还是一个很有才,也很会唱的人。没红真是可惜。 参加个好声音居然还不被人
待见,我挺为他叫屈的。
唱了很多遍都觉得离金志文的感觉有很大距离,马马虎虎交差了。唱得最好的应该是最
后的三句“啦”。
词曲,演唱 小文
你终于对我说分手
我们走到分岔路口
多希望这一秒永远停留
当你转身离开以后
我站在原地没有走
眼眶的泪水止不住的流
流着泪说分手 我不愿让你走
嘴边还有残留的爱没有问候
你却说走就走 狠心让爱这样到尽头
不愿让你走 我还没有罢休
我伤心的颤抖 这无力的双手
我只能够回忆 当初对你的曾经拥有
当你转身离开以后
我站在原地没有走
眼眶的泪水止不住的流
流着泪说分手 我不愿让你走
嘴边还有残留的爱没有问候
你却说走就走 狠心让爱这样到尽头
不愿让你走 我还没有罢休
我伤心的颤抖 这无力的双手
我只能够回忆 当初对你的曾经拥有
啦啦啦啦啦啦啦啦 啦啦啦啦
啦啦啦啦啦啦啦啦
avatar
a*2
4
达真堪布仁波切开示:
现在很多人学佛时间很长了,看似也很精进,也做了很多所谓的善事、功德,但是为
什么没有得到如是的功德利益呢?因为缺乏智慧,没有智慧的摄持。
若没有真实的智慧,也可以有相似的智慧。但是我们连相似的智慧都没有。我们在
修法时,做善事的时候,首先要观察自己的发心和动机。心善一切善,心恶一切恶。很
多时候,我们的发心和动机都是不正确的。有时没有什么发心和动机,是无记的状态。
有时有一些发心动机,但也没有无我和空性智慧的摄持。
比如闻法时,讲法者、所讲的法、闻法者自己都是显而无自性的。这只是显宗里讲
的境界。现在我们念诵的很多仪轨里,所讲的境界都是密宗的境界。按密宗的要求,进
大殿闻法或修法时,都要观五种圆满,这是密宗的发心。
我们讲“发心”的时候也都讲过显密共同与不共同的发心。显宗里,菩提心有世俗
谛菩提心和胜义谛菩提心,最好有胜义谛菩提心的摄持,要有智慧的摄持,保持这样的
见解。若是没有真实的智慧,也可以有相似的智慧,即能这样观想,保持这样的意念。
若是按密宗里讲的发心,就要观五种圆满。将一切观为清净圆满,大家这样做了吗
?比如闻法的时候,大殿就是无量宫殿、极乐世界,即住处圆满——清净刹土;本师圆
满就是佛;眷属圆满,都是男女本尊之性,都是佛菩萨;时间圆满,本来常有的相续轮
,远离三时——现在时、过去时、未来时,远离分别;法圆满,是大乘法、大圆满法。
大家没有这样观吧?如果没有,肯定得不到如是的功德和利益。
avatar
f*5
6
有人告诉过你这题有解?
如果有的话,merge sort就不需要额外空间了吧

【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个?

avatar
f*u
7
和485一起交,40天以后就有可能了。
avatar
s*e
8
sf

【在 a***e 的大作中提到】
: 爱扣,亲家, 这歌你一点我就开始学了,一直学到今天,唱了好多遍才完成的。
: 金志文还是一个很有才,也很会唱的人。没红真是可惜。 参加个好声音居然还不被人
: 待见,我挺为他叫屈的。
: 唱了很多遍都觉得离金志文的感觉有很大距离,马马虎虎交差了。唱得最好的应该是最
: 后的三句“啦”。
: 词曲,演唱 小文
: 你终于对我说分手
: 我们走到分岔路口
: 多希望这一秒永远停留
: 当你转身离开以后

avatar
b*e
10
#ifndef MERGE_SORTED_ARRAY_H
#define MERGE_SORTED_ARRAY_H
#include
using namespace std;
/* problem statement:
* Given an array of n elements and an integer k where k* Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
* algorithm to sort in O(n) time and O(1) space.
*/
class MergeSortedArray
{
public:
// [begin, end), inflection is the beginning of the second sorted
beginning
void sort(int * begin, int * end, int * inflection)
{
if (begin >
avatar
e*0
11
终于来啦~俺等得好辛苦啊~~马上转热包子,话说饿SHI了
avatar
f*5
13
BTW,
sort->sort->sort...
it will not be O(1) space.
each time,you may shorten your array,i assume that by average
you need log2n times to finish
it may be considered as O(log2n) extra space.(for call stack)

an

【在 b********e 的大作中提到】
: #ifndef MERGE_SORTED_ARRAY_H
: #define MERGE_SORTED_ARRAY_H
: #include
: using namespace std;
: /* problem statement:
: * Given an array of n elements and an integer k where k: * Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: * algorithm to sort in O(n) time and O(1) space.
: */
: class MergeSortedArray

avatar
l*d
14
第一次听这歌。 大头哥唱得很好,俺就不用去听原唱了。 :)
avatar
i*e
16
批判一下我的程序
假设数组是[0..k-1], [k..n-1],这样看起来舒服一些
第一个是递归的形式,尾递归所以空间没问题,第二个改写成了循环
考虑最差情况,k=1,这时候时间复杂度是O(n)
using namespace std;
void sort_recurse(int a[], int n, int k)
{
int ll = k, lr = n - k;
if (ll == 0 || lr == 0) {
return;
}
if (ll == lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[k+i]);
return;
} else if (ll < lr) {
for (int i = 0; i < ll; ++i)
swap(a[i], a[n-k+i]);
return sort_recurse(a, n - ll, k);
} else {
avatar
e*0
17
大头这唱得很入心很温油,超赞!
话说这歌几乎全吉他伴奏,节奏还是挺不好跟的,大头跟得很不错!
avatar
w*h
18
只有F7D7302的了
avatar
f*5
19
please check whether your code work well with below array
1,6,7,2,3,4,5,8
BTW,why 尾递归所以空间没问题?
recursion will use extra space

【在 i*****e 的大作中提到】
: 批判一下我的程序
: 假设数组是[0..k-1], [k..n-1],这样看起来舒服一些
: 第一个是递归的形式,尾递归所以空间没问题,第二个改写成了循环
: 考虑最差情况,k=1,这时候时间复杂度是O(n)
: using namespace std;
: void sort_recurse(int a[], int n, int k)
: {
: int ll = k, lr = n - k;
: if (ll == 0 || lr == 0) {
: return;

avatar
z*n
20
唱得很认真&森情,这吉他伴奏也很不错,这类歌混响再小一点可能会更好听。。。
avatar
d*e
21
idesire的程序我还没看,但前面betterlate的好像是对的,不过他的while那部分我暂
时还没想得清楚,而他用的是tail recursion,所以空间方面没问题。

【在 f*********5 的大作中提到】
: please check whether your code work well with below array
: 1,6,7,2,3,4,5,8
: BTW,why 尾递归所以空间没问题?
: recursion will use extra space

avatar
f*n
22
大头的声音听着很年轻啊~哈哈~这首不错
avatar
I*A
23
你能不能说一下betterlate的思路
为什么(*p2 < *p3)就要swap p2 and p1?

【在 d**e 的大作中提到】
: idesire的程序我还没看,但前面betterlate的好像是对的,不过他的while那部分我暂
: 时还没想得清楚,而他用的是tail recursion,所以空间方面没问题。

avatar
a*o
24
唱得很好,差的是后期那个混响。

【在 a***e 的大作中提到】
: 爱扣,亲家, 这歌你一点我就开始学了,一直学到今天,唱了好多遍才完成的。
: 金志文还是一个很有才,也很会唱的人。没红真是可惜。 参加个好声音居然还不被人
: 待见,我挺为他叫屈的。
: 唱了很多遍都觉得离金志文的感觉有很大距离,马马虎虎交差了。唱得最好的应该是最
: 后的三句“啦”。
: 词曲,演唱 小文
: 你终于对我说分手
: 我们走到分岔路口
: 多希望这一秒永远停留
: 当你转身离开以后

avatar
d*e
25
这个就是我不明白的地方。
之前试了几个例子也是对的,不过我现在找到例子,他的程序错了。
比如3,4,5,6,1,2,7,最后的结果只是1,2,3,5,6,4,7
开始他可能是手误,if没加上判断 begin==inflection,否则如果array本来就是排好
的,比如1,2, 3, 4, 5,6,7,那么会进入死循环。不过这个问题不是很大。
我不是很明白while loop里面的,也就是你问的这个问题。最好betterlate可以说明一
下。

【在 I**A 的大作中提到】
: 你能不能说一下betterlate的思路
: 为什么(*p2 < *p3)就要swap p2 and p1?

avatar
a*e
26
更新了混响,你再听听。链接没变。

【在 a****o 的大作中提到】
: 唱得很好,差的是后期那个混响。
avatar
d*e
27
赞成你的说法,应该是无解。
呼唤大牛出来确认一下 :)

【在 f*********5 的大作中提到】
: 有人告诉过你这题有解?
: 如果有的话,merge sort就不需要额外空间了吧

avatar
l*e
28
赞大头的深情演绎,好听。
avatar
s*t
29
p2上存的数只可能来自之前p1上存的数,因为这个数比p3大,
所以被替换到p2上,如果现在p2比当前p3的数小,那么肯定p2是最小值。
所以要swap p2 and p1.

【在 I**A 的大作中提到】
: 你能不能说一下betterlate的思路
: 为什么(*p2 < *p3)就要swap p2 and p1?

avatar
s*t
30
I see, you are right.
His code could not handle this case.

【在 d**e 的大作中提到】
: 这个就是我不明白的地方。
: 之前试了几个例子也是对的,不过我现在找到例子,他的程序错了。
: 比如3,4,5,6,1,2,7,最后的结果只是1,2,3,5,6,4,7
: 开始他可能是手误,if没加上判断 begin==inflection,否则如果array本来就是排好
: 的,比如1,2, 3, 4, 5,6,7,那么会进入死循环。不过这个问题不是很大。
: 我不是很明白while loop里面的,也就是你问的这个问题。最好betterlate可以说明一
: 下。

avatar
d*e
31
是的,运行的结果是错的。

【在 s*****t 的大作中提到】
: I see, you are right.
: His code could not handle this case.

avatar
p*u
32
这个问题是有解的。不过面试考这样的题,太不厚道了,完全是超出能力范围的题目。
这是TAOCP上的一个练习题,有一篇196x年的论文专门给了解法的。
基本思想是把数组分成 sqrt(n + m) 这样的块,然后重复利用空间。
1,前n个数有序,后m个数有序。把前n个数和后m个数,分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
3,对于作为swap空间的最后一个块,直接做冒泡排序。时间复杂度O(n + m),空间复杂度是O(1)的。
大致思想是上面这样的,具体细节我也记不清楚了。可以看看TAOCP,上面有习题解答。

【在 f*********5 的大作中提到】
: 有人告诉过你这题有解?
: 如果有的话,merge sort就不需要额外空间了吧

avatar
i*e
33
嗯,的确有问题
前些日子看到一道面试题,第一子题目是把一个有序数组给分段了,第二个是如何合并
,大致这个意思。所以先入为主了
删原帖

【在 f*********5 的大作中提到】
: please check whether your code work well with below array
: 1,6,7,2,3,4,5,8
: BTW,why 尾递归所以空间没问题?
: recursion will use extra space

avatar
d*e
34
牛!
看到我头晕

的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
复杂度是O(1)的。
答。

【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题,太不厚道了,完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题,有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块,然后重复利用空间。
: 1,前n个数有序,后m个数有序。把前n个数和后m个数,分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
: 3,对于作为swap空间的最后一个块,直接做冒泡排序。时间复杂度O(n + m),空间复杂度是O(1)的。
: 大致思想是上面这样的,具体细节我也记不清楚了。可以看看TAOCP,上面有习题解答。

avatar
l*e
35
nod,merge-sort O(1) space,太狠了

的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
复杂度是O(1)的。
答。

【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题,太不厚道了,完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题,有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块,然后重复利用空间。
: 1,前n个数有序,后m个数有序。把前n个数和后m个数,分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
: 3,对于作为swap空间的最后一个块,直接做冒泡排序。时间复杂度O(n + m),空间复杂度是O(1)的。
: 大致思想是上面这样的,具体细节我也记不清楚了。可以看看TAOCP,上面有习题解答。

avatar
d*e
36
请问一下是TACOP 的第几个volumn? thx

的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
复杂度是O(1)的。
答。

【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题,太不厚道了,完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题,有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块,然后重复利用空间。
: 1,前n个数有序,后m个数有序。把前n个数和后m个数,分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
: 3,对于作为swap空间的最后一个块,直接做冒泡排序。时间复杂度O(n + m),空间复杂度是O(1)的。
: 大致思想是上面这样的,具体细节我也记不清楚了。可以看看TAOCP,上面有习题解答。

avatar
y*n
37
TAOCP没找到.
avatar
c*n
38
I think you guys can stop wasting time on this,
if merge sort O(n) time O(1) space is possible, no one would use qsort
in ur step 2)
": 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做
swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。"
why is "空间复杂度是O(1)" ? the "swap" space u use, isn't it already
occupied by the last sqrt(n+m) block? even if u can use that block, it's
size sqrt(n+m)

的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
复杂度是O(1)的。
答。

【在 p*u 的大作中提到】
: 这个问题是有解的。不过面试考这样的题,太不厚道了,完全是超出能力范围的题目。
: 这是TAOCP上的一个练习题,有一篇196x年的论文专门给了解法的。
: 基本思想是把数组分成 sqrt(n + m) 这样的块,然后重复利用空间。
: 1,前n个数有序,后m个数有序。把前n个数和后m个数,分别划分成sqrt(n + m)大小的块。这样最多有sqrt(n + m)个块。
: 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
: 3,对于作为swap空间的最后一个块,直接做冒泡排序。时间复杂度O(n + m),空间复杂度是O(1)的。
: 大致思想是上面这样的,具体细节我也记不清楚了。可以看看TAOCP,上面有习题解答。

avatar
c*n
39
I take it back, found it
indeed it's very cryptic:
http://en.wikipedia.org/wiki/Merge_sort#CITEREFKatajainenPasanenTeuhola1996
search "Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical
in-place mergesort". Nordic Journal of Computing 3:"

【在 c******n 的大作中提到】
: I think you guys can stop wasting time on this,
: if merge sort O(n) time O(1) space is possible, no one would use qsort
: in ur step 2)
: ": 2,把前n个数的块和后m个数的块,做merge,用最后一个sqrt(n + m)大小的块做
: swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。"
: why is "空间复杂度是O(1)" ? the "swap" space u use, isn't it already
: occupied by the last sqrt(n+m) block? even if u can use that block, it's
: size sqrt(n+m)
:
: 的块。这样最多有sqrt(n + m)个块。

avatar
d*e
40
这个时间不是O(n)

【在 y****n 的大作中提到】
: TAOCP没找到.
avatar
y*n
41
没仔细看。
时间上O(n^2)了。

【在 d**e 的大作中提到】
: 这个时间不是O(n)
avatar
d*e
42
所以前面creation也说了,如果时间是O(n),空间是O(1),那其它sort不用也罢了。

【在 y****n 的大作中提到】
: 没仔细看。
: 时间上O(n^2)了。

avatar
w*a
43
这道题可不可以用in-place merge sort来解?当然需要两个指针first, second,查找
后分别指向需要swap的两个已排序的子数组的起始点,比如:
1 6 7 2 3 4 5 8 k=2, n=7, a[0..k] sorted, a[k+1..n] sorted
那么first指向6,second指向5,将“6 7 2 3 4 5”段swap,然后“5 4 3 2”和“7 6
”swap, 得到“2 3 4 5 6 7”,最后数组排好序:1 2 3 4 5 6 7 8
确定first和second:
first=0;
while (first <=k && a[first] < a[k+1]) first++;
second=k+1;maxmove=0;
while (second <=n && a[second] < a[first]) {second++;maxmove++;}
swap(a,first,second);
swap(a,first,first+maxmove);
swap(a,second-(k-first+1),second);
可以进一
avatar
p*u
44
是第三册的习题,讲排序的那一章。
严蔚敏版本的数据结构书,后面有个习题也是和这个类似,但是有一个特殊条件,前n
个数和后m个数的大小满足关系:n >= m * m
具体的大家可以去查一查课后习题,好像是在讲外部排序的那一章的习题吧,具体不太
记得了。

【在 d********e 的大作中提到】
: 请问一下是TACOP 的第几个volumn? thx
:
: 的块。这样最多有sqrt(n + m)个块。
: swap空间。这样下来的时间复杂度是O(n + m),空间复杂度是O(1)的。
: 复杂度是O(1)的。
: 答。

avatar
c*n
45
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
现成的code 大伙儿仔细看看吧

n

【在 p*u 的大作中提到】
: 是第三册的习题,讲排序的那一章。
: 严蔚敏版本的数据结构书,后面有个习题也是和这个类似,但是有一个特殊条件,前n
: 个数和后m个数的大小满足关系:n >= m * m
: 具体的大家可以去查一查课后习题,好像是在讲外部排序的那一章的习题吧,具体不太
: 记得了。

avatar
c*n
46
I see it now
I can understand the code, but the code is kind of different from the
paper from the Finnish guys.
the paper's most important point is "
given 2 sorted arrays, size N and M, Nwe need only a size N extra workspace to merge these 2"
but the following code does not utilize that assertion.
the code is fairly clear:
array_A, array_B, let's say size(array_A) > size(array_B)
then cut A into halves
A1 A2 B
then for the first element x of A2, find the largest element in B that
is small

【在 c******n 的大作中提到】
: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
: 现成的code 大伙儿仔细看看吧
:
: n

avatar
c*n
47
now I understand the Finnish paper:
just take the first element of the smaller array, x, binary search it in
the large one, find the prefix that's smaller than x, rotate first array
and the prefix, then you have
prefix < ( smaller array, what_is_left_of_the_bigger_array)
then treat the part of the smaller_array from second element on, and
recursively carry out this procedure.
in the end, each element is rotated at most once.

【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个?

avatar
c*n
48
the code for the Finnish paper algorithm
// O(n) time O(1) space merge of 2 arrays
//
public class smart_merge {
static int N=50;
//// return the largest i so that data[i]<= data[key_pos]
public static int lower(int data[] , int start, int key_pos ) {// we
know that the largest is 2N;
int end = N * 2;
start --; // if the return value is this one, that means
everything in the sub array is larger than key_pos
while ( start < end -1 ) {
int mid = ( s

【在 v******a 的大作中提到】
: Given an array of n elements and an integer k where k: Elements {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
: algorithm to sort in O(n) time and O(1) space.
: 怎么做这个?

avatar
d*e
49
谢谢。明天再仔细研究一下。

【在 c******n 的大作中提到】
: the code for the Finnish paper algorithm
: // O(n) time O(1) space merge of 2 arrays
: //
: public class smart_merge {
: static int N=50;
: //// return the largest i so that data[i]<= data[key_pos]
: public static int lower(int data[] , int start, int key_pos ) {// we
: know that the largest is 2N;
: int end = N * 2;
: start --; // if the return value is this one, that means

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。