专栏：https://cloud.tencent.com/developer/article/1845465 多关注多试试 image.png ... 展开详请

你是对的。 在QuickSelect之后的下一个候选人中，十进制占优：n / 10,2 * n / 10..9 * n / 10，因此只检查n / 10索引是不够的 请注意，显性占用在有序数组中长期运行，并且当然至少有一个具有提及索引的元素属于该运行。 例如k = 3，N = 11。让元素b占据至少1/3的数组。在这种情况下，排序数组可能看起来像 b b b b * * * * * * * * b b b b * * * * * * * * b b b b * * * * * * * * b b b b * * * * * * * * b b b b * * * * * * * * b b b b * * * * * * * b b b b * * * * * * * * b b b b * * * * * * * * b b b b ^ ^ //positions for quickselect ... 展开详请

首先要弄清楚,在Linux系统中,内核为每一个新创建的文件分配一个Inode(索引结点),每个文件都有一个惟一的inode号。文件属性保存在索引结点里，在访问文件时，索引结点被复制到内存在，从而实现文件的快速访问。 链接是一种在共享文件和访问它的用户的若干目录项之间建立联系的一种方法。Linux中包括两种链接：硬链接(Hard Link)和软链接(Soft Link),软链接又称为符号链接（Symbolic link）。 一、硬链接 硬链接说白了是一个指针，指向文件索引节点，系统并不为它重新分配inode。可以用:ln命令来建立硬链接。语法: ln [options] existingfile newfile ln[options] existingfile-list directory 用法: 第一种:为”existingfile”创建硬链接,文件名为”newfile”。第二种:在”directory”目录中,为”existingfile-list”中包含的所有文件创建一个同名的硬链接。常用可选[options] –f 无论”newfile”存在与否,都创建链接。-n 如果”newfile”已存在,就不创建链接。 下面举一些例子: $ ls –il 13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1 13059 -rwx - - - - - - 1 longcheng longcheng 57 8月 5 16:40 file2 $ ln file2 file2hard $ ls –il 13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard 注意在创建链接前,file1 显示的链接数目为1,创建链接后(1)file1和file1hard的链接数目都变为2;(2) file1和file1hard在inode号是一样的(3) file1和file1hard显示的文件大小也是一样。可见进行了ln命令的操作结果：file1和file1hard是同一个文件的两个名字，它们具有同样的索引节点号和文件属性，建立文件file1的硬链接，就是为file1的文件索引节点在当前目录上建立一个新指针。如下图,你可以删除其中任何一个,如rm file2 ,每次只会删除一个指针, 链接数同时减一,只有将所有指向文件内容的指针,也即链接数减为0时，内核才会把文件内容从磁盘上删除。当前目录逻辑结构：(不好意思图没有显示出来)。 还可以在不同目录，但同一文件系统中建立文件的硬链接。设file1、file2在目录/home/longcheng/dir1中，下面的命令，在/home/longcheng中建立file2的硬链接。 ln file2 /home/longcheng/file2hard 下面的程序，是将dir1目录中所有文件，在目录dir2中建立硬链接 $mkdir dir2 $ln /home/longcheng/dir1/* /home/longcheng/dir2 如果使用了 ln –f existingfile newfile,如果newfile已经存在，则无论原来newfile是什么文件，只用当前用户对它有写权限，newfile就成为exisitngfile的硬链接文件。 尽管硬链接节省空间，也是Linux系统整合文件系统的传统方式，但是存在一下不足之处：（1）不可以在不同文件系统的文件间建立链接（2）只有超级用户才可以为目录创建硬链接。虽然很多树上说root用户可以创建，但是笔者在学习过程中发现即使是root用户也不能创建，我的系统是Redhat，内核2.4、2.6都试过，在其他系统中不知道是不是可以。 二、软链接（符号链接） 符号链接是对一个文件的间接指针。硬链接直接指向文件的i节点。 软链接克服了硬链接的不足，没有任何文件系统的限制，任何用户可以创建指向目录的符号链接。因而现在更为广泛使用，它具有更大的灵活性，甚至可以跨越不同机器、不同网络对文件进行链接。 建立软链接，只要在ln后面加上选项 –s，下面举个例子 $ ls -il 13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard $ln –s file1 file1soft $ls -il 13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2 13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard 13061 lrwxrwxrwx 1 longcheng longcheng 5 8月 5 16:58 file1soft->file1 从上面链接后的结果可以看出来软链接与硬链接，区别不仅仅是在概念上，在实现上也是不同的。区别：硬链接原文件＆链接文件公用一个inode号，说明他们是同一个文件，而软链接原文件＆链接文件拥有不同的inode号，表明他们是两个不同的文件；在文件属性上软链接明确写出了是链接文件，而硬链接没有写出来，因为在本质上硬链接文件和原文件是完全平等关系；链接数目是不一样的，软链接的链接数目不会增加；文件大小是不一样的，硬链接文件显示的大小是跟原文件是一样的，这用强调，因为是等同的嘛，而这里软链接显示的大小与原文件就不同了，file1大小是48B，而file1soft是5B，这里面的5实际上就是“file1”的大小。 总之，建立软链接就是建立了一个新文件。当访问链接文件时，系统就会发现他是个链接文件，它读取链接文件找到真正要访问的文件。 在不同系统之间建立软链接、对目录建立链接，这里就不举例了，读者可以自己去尝试，我也是在不断实践中学习的。 当然软链接也有硬链接没有的缺点，因为链接文件包含有原文件的路径信息，所以当原文件从一个目录下移到其他目录中，再访问链接文件，系统就找不到了，而硬链接就没有这个缺陷，你想怎么移就怎么移；还有它要系统分配额外的空间用于建立新的索引节点和保存原文件的路径。补充一下：可以通过symlink来查看链接文件，可以用 man symlink来学习。... 展开详请

你的解释是正确的。这似乎是一个除了技术知识之外还考验你自信心的问题。 顺便说一句，如果你回答 这两个代码块都是同样快的，因为两者都需要无限的时间才能完成 面试官会说 但是while (1)可以每秒做更多的迭代; 你能解释为什么吗？（这是无稽之谈;再次测试你的信心） 所以通过像你这样回答，你节省了一些时间，否则你会在讨论这个不好的问题时浪费时间。 以下是我的系统上的编译器生成的示例代码（MS Visual Studio 2012），关闭了优化： yyy: xor eax, eax cmp eax, 1 (or 2, depending on your code) je xxx jmp yyy xxx: ... 优化开启后： xxx: jmp xxx 所以生成的代码是完全一样的，至少有一个优化的编译器。... 展开详请