题目来源:https://leetcode.com/problems/k-closest-points-to-origin/description/

标记难度:Easy

提交次数:2/5

代码效率:

  • 普通方法:80.0%(208ms)
  • 堆:60.00%(212ms)
  • 快排:40.00%(224ms)

题意

给定平面上的若干个(<=10000)点,求距离原点最近的K个点。保证结果对应的点集唯一,以任意顺序返回都可以。

分析

其实我睡过了这次比赛。随后又撞上期末考试和毕设,感觉流年不利。


显然可以把距离算出来之后排序,然后取前K个点,时间复杂度为O(N*log(N))

如果想做得更好一点的话,可以用一个大小为K的堆来维护距离前K小的点,时间复杂度为O(N*log(K))

题解里给出了一种神奇的方法,思路是用类似于快排的方法求前K小的点,感觉很有趣。不过为了严格起见,大概还是要每次随机选主元才行……[1]

快排!快排!

为了写好题解里快排的方法,浪费了一两个小时。我果然又把快排的写法忘光了!姑且先总结一下。

快排的第一种写法不妨称之为交替填坑法。这种做法的核心规律是,先把序列最靠左的元素拿出来作为主元(并空出来一个坑),然后从右向左找到第一个可以填这个坑的元素(也就是第一个比主元小的元素),把它拿出来填到这个坑里。此时右边就空出来一个新坑。然后从左边刚被填完的坑向右扫描,找到第一个能够填右边的坑的元素(也就是第一个比主元大的元素),把它拿出来填到右边的坑里。此时左边又空出来一个新坑……以此类推。最后中间剩下一个坑,满足左边的元素都比主元小,右边的元素都比主元大,再把主元填到这个坑里。

以序列[3, 6, 5, 4, 2, 1, 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
| 3 | 6 | 5 | 4 | 2 | 1 | 0 |
^
pivot

pivot = 3, remove pivot
| x | 6 | 5 | 4 | 2 | 1 | 0 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 6 | 5 | 4 | 2 | 1 | x |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | x | 5 | 4 | 2 | 1 | 6 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 1 | 5 | 4 | 2 | x | 6 |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | 1 | x | 4 | 2 | 5 | 6 |
i j

pivot = 3, move A[j] to A[i], i++
| 0 | 1 | 2 | 4 | x | 5 | 6 |
i j

pivot = 3, move A[i] to A[j], j--
| 0 | 1 | 2 | x | 4 | 5 | 6 |
i j

found i==j, put pivot into i (or j)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
i j

显然可以看出,每个周期包含两次指针移动和交换,其中ij的含义是分阶段而不同的。

此处有坑,明天再填。

2019.1.17 UPDATE:坑应该是填不动了。简单来说,还有一种常用的写法是不移出主元,而是让它在里面跟着交换。这两种写法都解决不了主元重复的问题,此时最好改成CLRS式的写法。

代码

普通方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<pair<int, int>> toSort;
for (int i = 0; i < points.size(); i++) {
toSort.emplace_back(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
}
sort(toSort.begin(), toSort.end());
vector<vector<int>> ans;
for (int i = 0; i < K; i++)
ans.push_back(points[toSort[i].second]);
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
priority_queue<pair<int, int>> q;
for (int i = 0; i < points.size(); i++) {
q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
if (q.size() > K) q.pop();
}
vector<vector<int>> ans;
while (!q.empty()) {
ans.push_back(points[q.top().second]);
q.pop();
}
return ans;
}
};

快排

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
class Solution {
private:
int dist(vector<int>& p) {
return p[0] * p[0] + p[1] * p[1];
}

void partition(vector<vector<int>>& points, int l, int r, int& K) {
if (l >= r) return;
if (l >= K) return;
if (r < K) return;
// int x = rand() % (r - l + 1) + l;
int x = l;
int i = l, j = r;
int pivot = dist(points[x]);
while (i < j) {
// why <, not <=?
while (dist(points[i]) < pivot && i < j) i++;
while (pivot < dist(points[j]) && i < j) j--;
if (i < j) swap(points[i], points[j]);
}
partition(points, l, i - 1, K);
partition(points, i + 1, r, K);
}

public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
partition(points, 0, points.size() - 1, K);
return vector(points.begin(), points.begin() + K);
}
};

  1. Leetcode Official Solution for 973. K Closest Points to Origin

题目来源:https://leetcode.com/problems/pancake-sorting/description/

标记难度:Medium

提交次数:1/1

代码效率:8ms

题意

给定一个数组A(其中的元素是[1, 2, ..., A.length]的排列),定义pancake flip操作为翻转A中前k个数,其中k <= A.length。要求通过最多10 * A.length词操作将A排序。求操作序列。

分析

比赛的时候我的想法很简单:因为每次操作影响的只有前k个数,所以不妨考虑先排好A中靠后的数,这样之后的操作就不会影响它们。于是就可以得到一个很显然的思路:需要把i放到i位置时,就找到i,先通过一次操作把它flip到数组开头,再通过一次操作把它flip到i位置。这样,操作次数最多为2 * A.length,符合要求。

以序列[3, 1, 5, 2, 4]为例:

  • 将5放到第5位:
    • flip 3:[5, 1, 3, 2, 4]
    • flip 5:[4, 2, 3, 1, 5]
  • 将4放到第4位:
    • flip 1(不需要)
    • flip 4:[1, 3, 2, 4, 5]
  • 将3放到第3位:
    • flip 2:[3, 1, 2, 4, 5]
    • flip 3:[2, 1, 3, 4, 5]
  • 将2放到第2位:
    • flip 1(不需要)
    • flip 2:[1, 2, 3, 4, 5]
  • 将1放到第1位(已经在第1位了)

这是一种非常straightforward的方法,题解也是这么做的。

而且显然上述方法已经说明,flip操作能够将任意排列变换成其他任意排列。

我的问题是:

  1. 直接模拟的复杂度为O(N^2)(因为每次翻转操作的复杂度是O(N)),能否降低复杂度?
  2. 这样得到的是否为最优解?

第二个问题的答案是,显然不是,这种做法只是给出了一个上界(至多2*N - 3次翻转必然可以完成排序,至于为什么少了3次,请考虑只剩1和2时的情形)。而且找到最优解是一个NP-难问题。那么我就不再耗费我可怜的脑细胞在这个问题上了。顺便一提,比尔·盖茨证明了这个问题的上界是5(N+5) / 3;目前最优的结果是18N / 11[1]

经过一些思考和查找资料,我认为我目前无法回答第一个问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
vector<int> ans;
void flip(int k, vector<int>& A) {
for (int i = 0; i < k - i - 1; i++)
swap(A[i], A[k - i - 1]);
ans.push_back(k);
}

public:
vector<int> pancakeSort(vector<int>& A) {
int n = A.size();
for (int i = n; i >= 1; i--) {
// put i on place i
int index = 0;
while (A[index] != i && index < n) index++;
if (index == i - 1) continue;
flip(index + 1, A);
flip(i, A);
}
return ans;
}
};

  1. 原来Pancake Sorting这个名字并不是乱起的!wikipedia - Pancake sorting

题目来源:https://leetcode.com/problems/reorder-log-files/description/

标记难度:Easy

提交次数:1/2

代码效率:12ms

题意

给定一堆log和排序方法,返回排序之后的结果。

分析

这次比赛的排名是528 / 3720。第一题错了一次,然后第四题没有想出正解。这次比赛比较迷的一点是,它推迟了,改成了10:30开始,然后我的电脑中间还没网了,不得不重启一次……


这道题的考点可以用“Custom Sort”来概括,也许考察语言特性和细节比算法本身要多。然后因为搞错了identifier具体的排序方法还WA了一次。没别的了。

代码

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
class Solution {
private:

struct Log {
string s;
string identifier;
vector<string> words;
string word;
bool isLetter;
int index;

Log() {}

Log(string s, int i) {
this->s = s;
this->index = i;
stringstream lineStream(s);

lineStream >> identifier;

string token;
isLetter = true;
while (lineStream >> token)
{
words.push_back(token);
word += token;
if (isNumeric(token))
isLetter = false;
}
}

bool isNumeric(string s) {
for (char ch: s)
if (ch < '0' || ch > '9') return false;
return true;
}

friend bool operator < (const Log& l1, const Log& l2) {
if (l1.isLetter != l2.isLetter) {
if (l1.isLetter) return true;
else return false;
}
if (l1.isLetter && l2.isLetter) {
int i = 0, n = min(l1.words.size(), l2.words.size());
for (i = 0; i < n; i++)
if (l1.words[i] != l2.words[i])
return l1.words[i] < l2.words[i];
if (l1.words.size() != l2.words.size())
return l1.words.size() < l2.words.size();
return l1.identifier < l2.identifier;
}
return l1.index < l2.index;
}
};

public:
vector<string> reorderLogFiles(vector<string>& logs) {
vector<Log> Logs;
for (int i = 0; i < logs.size(); i++) {
Logs.emplace_back(logs[i], i);
}
sort(Logs.begin(), Logs.end());
vector<string> ans;
for (Log log: Logs)
ans.push_back(log.s);
return ans;
}
};