By

最近在做一个站内搜索功能,有用到一个分页功能.搜索时会传两个参数pageId和pageSize 用来指定页号与每页的条数.solr已经提供了start和rows两个参数,于是将分页参数与之对应起来,在component初始化时写了如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
String pidStr = req.getParams().get(PAGE_ID);
if ( pidStr != null ) { 
    int pageId = req.getParams().getInt(PAGE_ID, 0);
    int pageSize = req.getParams().getInt(PAGE_SIZE, 10);
    pageId = (pageId > -1) ? pageId : 0; 
    pageSize = (pageSize > 0 ) ? pageSize : 10; 
    ModifiableSolrParams params = new ModifiableSolrParams(req.getParams());
    params.set(CommonParams.START, pageId * pageSize);
    params.set(CommonParams.ROWS, pageSize);
    params.set(CommonParams.WT, "json");
    params.set(CommonParams.OMIT_HEADER, "true");
    req.setParams(params);
}

可是一直得不到正确的结果，在后台输出日志,发现start和rows在设置了上面的值后，start和rows会用来构建新的查询,在新的查询中start会变为0,而rows会变成start与rows的和，可是之后start和rows又会变成原先的值，于是得不到想要的结果。

举个例子,假设要搜第三页,每页10条,则可设置pageId为2,pageSize为10,于是start被设置成20,rows被设置成10,之后start和rows会被用于生成向shard发送的请求,start被设置为0,rows设置为30.问题在于这个请求发出之后start的值又变成了20,rows变成了10,百思不得其解.

跟踪代码到createMainQuery函数,看到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
if (rb.shards_start > -1) {
    // if the client set shards.start set this explicitly
    sreq.params.set(CommonParams.START, rb.shards_start);
} else {
    sreq.params.set(CommonParams.START, "0");
}
if (rb.shards_rows > -1) {
    // if the client set shards.rows set this explicity
    sreq.params.set(CommonParams.ROWS, rb.shards_rows);
} else {
    sreq.params.set(CommonParams.ROWS, rb.getSortSpec().getOffset()
            + rb.getSortSpec().getCount());
}

打印日志rb.shards_start与rb.shards_rows都为-1,于是start变为0,row变成30,这是正确的,那么关键点就是要找出start和rows何时变成20与10，跟踪程序找不到原因。看后台日志,发现初始化每次都会执行两次,然后想到分布式，才渐渐明白问题的原因.

在一次分布式查询中,solr的leader会接受请求，然后对请求进行解析，之后重新构建请求，将新的请求发给各个Shard,Shard做非分布式查询之后,将结果发给leader,之后leader汇总各个Shard的响应,进行最后的处理(如做offset等),问题是leader和Shard都是同一份代码,而且初始化部分每个Shard接收leader的请求后都要执行,于是start和rows又被重新设置了.在上面的例子中,start和rows在Shard中分别被设置成20和10了,只会Shard做非分布式查询,这样Shard只会返回10条数据给leader，这显然不是想要的.

之后发现,在leader构建的新的请求中,会添加isShard=true参数,于是可以修改代码如下:

1
2
boolean isShard = req.getParams().getBool(ShardParams.IS_SHARD, false);
if ( pidStr != null && !isShard) { //分布式时，只有leader才需要执行这里

之后结果就是正确的。到这里，才有点明白分布式程序，真不好写.

联系作者

By

工作一年后,才知道有Screen这个东西,太不应该了,也许真是环境影响人.

今天遇到问题,导师过来指导,看我的SecureCRT开着很多个会话,没有用Screen,于是提醒可以用这个.之前在公司的wiki上看到过介绍,本以为就是SecureCRT,原来是一个管理会话工具,有了它之后,就不需要再开很多个会话,然后关闭了.会话间的切换也可以很方便的用快捷键命令,而不是鼠标,因为鼠标极其影响效率.

用了公司一个员工的配置
hardstatus alwayslastline “%{=b}%{b}%-w%{.BW}%10>%n*%t%{-}%+w%< %=%{kG}%C%A, %Y-%m-%d”
screen -t local1 0 bash
screen -t local2 1 bash
screen -t local3 2 bash
screen -t local4 3 bash
screen -t local5 4 bash

select 0

vim ~/.screenrc,复制上面内容.之后就可以使用Screen了.一些常用命令如下:
c-a : Ctrl + a
screen -S name #开一个session
screen -S name -X quit #杀死session
c-a c #创建一个窗口
c-a n #next 窗口
c-a p #previous 窗口
c-a A #为窗口命名
c-a d #detach screen
c-a #跳转到number的窗口
screen -ls #查看窗口
screen -r name #连接一个session
screen -x name #共享session
可以参考http://hunsefee.diandian.com/post/2010-10-28/7319178

联系作者

By

开始Lucene之路,从官网下了最新的4.9.0,从先从小例子开始.
建索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package org.dsl;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.TextField;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig.OpenMode;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.util.Version;
import java.io.File;
import java.io.IOException;
public class Index {
    public static void main(String[] args) throws IOException {
        String INDEX_DIR = "e:\\index";
        Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_4_9);
        IndexWriterConfig iwc = new IndexWriterConfig(Version.LUCENE_4_9, analyzer);
        IndexWriter writer = null;
        iwc.setOpenMode(OpenMode.CREATE);
        iwc.setUseCompoundFile(false);
        try {
            writer = new IndexWriter(FSDirectory.open(new File(INDEX_DIR)), iwc);
            Document doc = new Document();
            doc.add(new TextField("title", "who are you, you are a man", Field.Store.YES));
            doc.add(new TextField("content", "A long way to go there. Please drive a car", Field.Store.NO));
            writer.addDocument(doc);
            doc = new Document();
            doc.add(new TextField("title", "are you sure", Field.Store.YES));
            doc.add(new TextField("content", "He is a good man. He is a driver", Field.Store.NO));
            writer.addDocument(doc);
            writer.commit();
            writer.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}

搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package org.dsl;
import java.io.File;
import java.util.Date;
import org.apache.lucene.document.Document;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.store.FSDirectory;
public class Search {
    private Search() {}
    public static void main(String[] args) throws Exception {
        String index = "e:\\index";
        IndexReader reader = DirectoryReader.open(FSDirectory.open(new File(index)));
        IndexSearcher searcher = new IndexSearcher(reader);
        String queryString = "driver";
        Query query = new TermQuery(new Term("content", queryString));
        System.out.println("Searching for: " + query.toString());
        Date start = new Date();
        TopDocs results = searcher.search(query, null, 100);
        Date end = new Date();
        System.out.println("Time: "+(end.getTime()-start.getTime())+"ms");
        ScoreDoc[] hits = results.scoreDocs;
        int numTotalHits = results.totalHits;
        System.out.println(numTotalHits + " total matching documents");
        for (int i = 0; i < hits.length; i++) {
            String output = "";
            Document doc = searcher.doc(hits[i].doc);
            output += "doc="+hits[i].doc+" score="+hits[i].score;
            String title = doc.get("title");
            if (title != null) {
                output += " " + title;
            }
            System.out.println(output);
        }
        reader.close();
    }
}

联系作者

By

还在学校的时候，绍祝师兄每次面试回来，如果有趣题都会和我讨论，因为正好坐他边上，记得这题也是那时讨论的一题。记得当时想了一会后就做出来了。只是时隔多年，再次遇到这题，已经忘记当初是怎么做了。

题目很简单，对于3 打印
1 2 3
8 9 4
7 6 5
对于4，打印
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
​​
观察之后发现规律，先是向右一直走，之后向下一直走，之后向左，最后向上，每次变换方向的原因有两个，一个是走到矩形的边界，另一个是沿着这个方向走，前面的一个位置已经走过了。在当前位置，要找下一个有效位置，只需按顺序遍历上面四个方向即可。写成代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def spiral_number(N):
    step_x = [0, 1, 0, -1]
    step_y = [1, 0, -1, 0]
    a = [[0 for j in xrange(N)] for j in xrange(N)]
    dir = 0
    i = 0
    j = 0
    a[i][j] = 1
    n = 2
    while n <= N ** 2:
        x = i + step_x[dir]
        y = j + step_y[dir]
        if x >= 0 and x < N and y >= 0 and y < N and a[x][y] == 0:
            a[x][y] = n
            n += 1
            i = x
            j = y
        else:
            dir = (dir + 1 + len(step_x)) % len(step_x)

    for i in xrange(N):
        for j in xrange(N):
            print a[i][j],
        print

spiral_number(4)

联系作者

By

在pythontip上做题时,有这样一道题，
给你一个正整数N(1 <= N <= 10000000)，求{1,2,3,…,N}中质数的个数。
如N=3， 输出2.
也就是求N以内质数的个数。
刚开始用以前写的筛法写了一个最初版本，

1
2
3
4
5
6
7
8
9
10
11
N = 10000000
primes = [True for i in xrange(N + 1)] 
primes[0] = primes[1] = False
for i in xrange(2, N + 1): 
    if not primes[i]:
        continue
    n = i * i 
    while n < N + 1:
        primes[n] = False
        n += i
print len([i for i in xrange(N + 1) if primes[i]])

发现超时，用time模块的clock测试,用了16s.之后一步一步优化，先将len([i for i in xrange(N + 1) if primes[i]])这句改成primes.count(True)时间缩短到14s,之后看了讨论组里的讨论,将

1
2
3
4
n = i * i 
    while n < N + 1:
        primes[n] = False
        n += i

这部分改成

1
primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1)

时间没有明显的变化，因为看到[False] ((N - i i) / i + 1)，于是将[True for i in xrange(N + 1)] 这行改成[True] * (N + 1) ，速度明显加快，只用了4s,经过这样优化后，程序变成了

1
2
3
4
5
6
7
8
N = 10000000
primes = [True] * (N + 1) 
primes[0] = primes[1] = False
for i in xrange(2, N + 1): 
    if not primes[i]:
        continue
    primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1)
print primes.count(True)

之后想办法将for循环去掉。于是将它改成

1
2
3
4
5
i = 2
while i * i <= N:
    if primes[i]:
        primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1)
    i += 1

最终为

1
2
3
4
5
6
7
8
9
N = 10000000
primes = [True] * (N + 1) 
primes[0] = primes[1] = False
i = 2
while i * i <= N:
    if primes[i]:
        primes[i * i:N + 1:i] = [False] * ((N - i * i) / i + 1)
    i += 1
print primes.count(True)

时间跑到了2s以内，提交后通过了。

之后将之前求素数的程序筛法得到素数进行修改,得到

1
2
3
4
5
6
7
8
9
def getPrimes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    i = 2
    while i * i <= n:
        if primes[i]:
            primes[i * i:n + 1:i] = [False] * ((n - i * i) / i + 1)
        i += 1
    return [i for i in xrange(n + 1) if primes[i]]

​

联系作者

By

昨天去面试，面试官出了一道最大连续子序列的题目后，很快就做出来，因为前不久还做过笔记的。之后出了一道，最大子矩阵的题目。也就是给出一个矩阵，如：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
求它的子矩阵的最大和。
如
9 2
-4 1
-1 8
是最大子矩阵，和为15.​

想了一会之后，找到了一个转化为最大连续子序列的办法。也就是先对列求和，之后再用最大连续子序列的方法。给出这个办法后，还想考虑优化，只是一直想不出来。回来之后，想起编程之美上有类似的题目，看了之后，没想到已经是最优的了。又想起以前在POJ应该做过类似的题目，于是找到了POJ1050- To The Max. 编写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#define N 100
int a[N][N];
int b[N];
int max_sub_array(int *a, int n) {
    int max_sum = a[0];
    int sum = a[0];
    for (int i = 1; i < n; i++) {
        if (sum < 0) {
            sum = 0;
        }
        sum += a[i];
        if (sum > max_sum) {
            max_sum = sum;
        }
    }
    return max_sum;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int max_sum = -127 * 100 * 100;
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            b[k] = 0;
        }
        for (int j = i; j < n; j++) {
            for (int k = 0; k < n; k++) {
                b[k] += a[j][k];
            }
            int sum = max_sub_array(b, n);
            if (sum > max_sum) {
                max_sum = sum;
            }
        }
    }
    printf("%d\n", max_sum);
    return 0;
}

联系作者

By

AC自动机作为多模式匹配的经典方法，在关键词过滤中有重要应用，在我看来，AC自动机主要是这样几个步骤，第一步是先建立关键词的trie数，第二步是构建自动机，建立关键词之间的联系，第三步是利用第二步构建的自动机进行检索。HDU2222-关键词搜索是AC自动机的一个简单应用。关于AC自动机的资料，可以看这里http://www.notonlysuccess.com/index.php/aho-corasick-automaton/.
问题描述
现在，搜索引擎如谷歌，百度等已经走进每个人的生活。
Wiskey也想在他的图片检索系统中实现这个功能。
每一张图片有一段描述，当用户输入关键字查找图片时，系统会将这些关键字与图片的描述进行匹配，然后显示与这些关键字最匹配的图片。
为了简化用题，这里给你出一段图片的描述，和一些关键字，请你告诉我​将匹配多少个关键字。
输入
第一行是一个整数，它的意思是有多少个测试用例。
每一个测试用例包含整数N，它的意思是有多少个关键字。(N <= 10000)
每一个关键字是由’a’-‘z’的字符组成，长度不超过50.
用例的最后一行​是描述，长度不超过1000000.
示例输入
1
5
she
he
say
shr
her
yasherhs
示例输出
3

解法：
AC自动机的简单应用。有一个坑是，输入中关键词存在重复时，要计算多次。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int NUM = 26;
struct NODE {
    int cnt;
    NODE *fail;
    NODE *next[NUM];
    NODE () {
        cnt = 0;
        fail = NULL;
        memset(next, 0, sizeof(next));
    }
};

void insert(NODE *root, char *s) {
    NODE *cur = root;
    while (*s) {
        int index = *s - 'a';
        if (!cur->next[index]) {
            cur->next[index] = new NODE();
        }
        cur = cur->next[index];
        s++;
    }
    cur->cnt++;
} 
void ac_build(NODE *root) {
    queue <NODE *> q;
    NODE *cur;
    root->fail = NULL;
    for (int i = 0; i < NUM; i++) {
        if (root->next[i]) {
            root->next[i]->fail = root;
            q.push(root->next[i]);
        }
    } 
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        for (int i = 0; i < NUM; i++) {
            if (cur->next[i]) {
                q.push(cur->next[i]);
                NODE *temp = cur->fail;
                while (temp) {
                    if (temp->next[i]) {
                        cur->next[i]->fail = temp->next[i];
                        break;
                    }
                    temp = temp->fail;
                }
                if (temp == NULL) {
                    cur->next[i]->fail = root;
                }
            }
        }
    }
}
int ac_find(NODE *root, char *s) {
    int sum = 0;
    NODE *cur = root;
    while (*s) {
        int index = *s - 'a';
        while (cur->next[index] == NULL && cur != root) {
            cur = cur->fail;
        }
        cur = (cur->next[index] == NULL) ? root : cur->next[index]; 
        NODE *temp = cur;
        while (temp != root && temp->cnt != -1) {  
            sum += temp->cnt;
            temp->cnt = -1;
            temp = temp->fail;
        }
        s++;
    }
    return sum;
}
int main() {
    int ncase, n;
    char word[51];
    char desc[1000001];
    scanf("%d", &ncase);
    while (ncase--) {
        NODE *root = new NODE();
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", word);
            insert(root, word);
        }
        scanf("%s", desc);
        ac_build(root);
        int res = ac_find(root, desc);
        printf("%d\n", res);
    }
    return 0;
}

联系作者

By

Trie又称为前缀树或字典树，它有许多重要用途，如搜索提示，以及作为AC自动机的基础。POJ2001-最短前缀这题是Trie的基础应用。
Description
A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.

An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”.
Input
The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.
Output
The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
​​​​​描述
一个字符串的前缀是从头开始的字符串的子串。”carbon”的前缀有：”c”,”ca”,”car”,”carb”,”carbo”和”carbon”.注意在这个问题中空串不认为是前缀，但是每个非空字符串自身可以认为是一个前缀。在日常用于中，我们倾向于用前缀来缩写词。例如，“carbohydrate”常缩写成”carb”.在这个问题中，我们给出一系列单词，要求能够唯一标识单词的最短前缀。

例如在下面的例子中，”carbohydrate”可以缩写成”carboh”,但是它不能缩写成”carbo”(或者更短),因为在这些词中，还有一个词是由”carbo”开始的.

精确匹配将覆盖前缀匹配。例如，前缀”car”精确匹配单词”car”.因此,”car”可以毫无歧义的认为是”car”的简写,而不是”carriage”的，或者其它一些由”car”作为前缀的单词.
输入：
输入至少包含两个，不超过1000行，每行宝行一个由1到20个字母组成的单词。
输出：
输出包含与输入相同的行数。每一行输出由对应的输入组成，跟着一个空格，之后是唯一(无歧义)标示单词的最短前缀.
示例输入：
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
示例输出：
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
解答：
在节点中增加一个time字段来记录路径被经过的次数，如果time=1,则只出现一次，说明可以用来标示单词，作为最短前缀。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include
#include
#include
using namespace std;
const int NUM = 26;
const int MAX = 1000;
const int LENGTH = 21;
char words[MAX][LENGTH];
struct NODE {
    int time;
    NODE *next[NUM];
    NODE () {
        time = 0;
        memset(next, 0, sizeof(next));
    }
};

void insert(NODE *root, char *s) {
    NODE *cur = root;
    while (*s != '\0') {
        int index = *s - 'a';
        if (!cur->next[index]) {
            cur->next[index] = new NODE();
            cur = cur->next[index];
            cur->time = 1;
        } else {
            cur = cur->next[index];
            (cur->time)++;
        }
        s++;
    }
}
void search(NODE *root, char *s) {
    NODE *cur = root;
    while (*s != '\0') {
        int index = *s - 'a';
        cur = cur->next[index];
        if (cur->time != 1) {
            printf("%c", *s);
            s++;
        } else {
            printf("%c", *s);
            break;
        }
    }
    printf("\n");
}
int main() {
    int total = 0;
    NODE * root = new NODE();
    while (scanf("%s", words[total]) != EOF) {
        insert(root, words[total]);
        total++;
    }
    for (int i = 0; i < total; i++) {
        printf("%s ", words[i]);
        search(root, words[i]);
    }
    return 0;
}

联系作者

By

对于求最大的K个数和最小的K个数，一个解决的办法是使用堆，这里以最小的K个数为例。
题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

输入：
每个测试案例包括2行：
第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。
第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。

输出：
对应每个测试案例，输出最小的k个数，并按从小到大顺序打印。

样例输入：
8 4
4 5 1 6 2 7 3 8
样例输出：
1 2 3 4

对于这题，可以使用堆来解决。首先建立一个K个元素的大顶堆，对于之后的n-k个元素，每个与堆顶比较，如果大于堆顶，则它不可能是最小的K个数之一，如果小于堆顶，则将堆顶替换，并重建大顶堆。之后剩下的K个元素就是最小的K个数。对它们从小到大排序就可以得到结果。
写成代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
void adjust_heap(int *a, int cur, int n) {
    int left, right;
    while (true) {
        left = 2 * cur + 1;
        right = 2 * cur + 2;
        int index = cur;
        if (left < n && a[left] > a[index]) {
            index = left;
        }
        if (right < n && a[right] > a[index]) {
            index = right;
        }
        if (index != cur) {
            swap(a[cur], a[index]);
            cur = index;
        } else {
            break;
        }
    }
}
void build_heap(int *a, int n) {
    for (int i = (n - 1) / 2; i >= 0; i--) {
        adjust_heap(a, i, n);
    }
}
void heap_sort(int *a, int n) {
    build_heap(a, n);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        adjust_heap(a, 0, i);
    }
} 
int main() {
    int n, k, num;
    while(scanf("%d %d", &n, &k) != EOF) {
        int *a = new int[k];
        for (int i = 0; i < n; i++) {
            scanf("%d", &num);
            if (i <= k - 1) {
                a[i] = num;
                if (i == k - 1) {
                    build_heap(a, k);
                }
            } else {
                if (a[0] > num) {
                    swap(a[0], num);
                    adjust_heap(a, 0, k);
                }
            }
        }
        heap_sort(a, k);
        for (int i = 0; i < k - 1; i++) {
            printf("%d ", a[i]);
        }
        printf("%d\n", a[k - 1]);
        delete[] a;
    }
    return 0;
}

联系作者

By

对于求最小的K个数和最大的K个数，一种解决办法是使用堆。对于堆，数据结构的书籍中都有讲到，可是面试时不知是紧张还是什么原因，连堆都忘记了，悲哀，真是悲哀。

想来堆排序还是不难的，如果要对n个数字从小到大排序，则先建立这n个数字的大顶堆，之后堆顶与最后一个数字交换，此时就得到最大的数字，且在最后一位中，之后之需要对前n-1个数字排序。这里堆顶与最后一个数字交换后，会破坏了大顶堆，需要重建堆。对于大顶堆，意思就是堆顶的元素是最大的，之后是堆顶的左右子节点。

这里主要就是两个步骤，一个是建立大顶堆，一个是重建堆。
看代码可能会更容易一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <stdlib.h>
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
void adjust_heap(int *a, int cur, int n) {
    int left, right;
    while (true) {
        left = 2 * cur + 1;
        right = 2 * cur + 2;
        int index = cur;
        if (left < n && a[left] > a[index]) {
            index = left;
        }
        if (right < n && a[right] > a[index]) {
            index = right;
        }
        if (index != cur) {
            swap(a[cur], a[index]);
            cur = index;
        } else {
            break;
        }
    }
}
void build_heap(int *a, int n) {
    for (int i = (n - 1) / 2; i >= 0; i--) {
        adjust_heap(a, i, n);
    }
}
void heap_sort(int *a, int n) {
    build_heap(a, n);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        adjust_heap(a, 0, i);
    }
} 
int main() {
    int a[] = {10, 2, 5, 7, 6, 13 , 8, 7};
    int n = sizeof(a) / sizeof(int);
    heap_sort(a, n);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n - 1]);
    return 0;
}

联系作者