Tag Archives: 排序

LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

给定二维平面上的若干个点,求距离原点最近的K个点。

看总结: https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/cyu-yan-san-chong-jie-fa-han-zong-jie-by-gan-cui-j/

事实上,诸如此类的,要在一个数组中寻找第K大的数(或者第K小的数),前K大的数,前K小的数,一般来说的方法有:

1.先排序(快排)时间复杂度为nlogn
2.建堆,堆的大小为K,建立大根堆或者小根堆,时间复杂度为nlogK(如果要求出前K个较大的,那么就建立小根堆,一旦比堆顶大,那么就入堆);
3.结合快速排序划分的方法,不断减小问题的规模

对于这一题,采用解法3,即快排划分的思路。采用标准快排思路,每次选区间最右边的元素作为pivot,然后划分,看看划分后的pivot位置和K的大小关系,递归在左右区间进行划分。完整代码如下:

class Solution {
private:
	vector<int> origin;

	int CalDist(vector<int> &p1, vector<int> &p2) {
		return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
	}

	void MySwap(vector<vector<int>>& points, int u, int v) {
		swap(points[u][0], points[v][0]);
		swap(points[u][1], points[v][1]);
	}

	void Work(vector<vector<int>>& points, int l, int r, int K) {
		if (l >= r) return;

		int pivot = r;
		int pdist = CalDist(points[pivot], origin);
		int i = l;
		for (int j = l; j < r; ++j) {
			int idist = CalDist(points[j], origin);
			if (idist < pdist) {
				MySwap(points, i++, j);
			}
		}
		MySwap(points, i, pivot);

		if (K == i)return;
		else if (K < i)Work(points, l, i - 1, K);
		else Work(points, i + 1, r, K);
	}
public:
	vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
		origin = { 0, 0 }; // 求与该点距离最近的top-k个点,本题中该点是原点

		for (int i = 0; i < points.size(); ++i) {
			printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
		}

		Work(points, 0, points.size() - 1, K - 1);

		vector<vector<int>> ans;
		for (int i = 0; i < K; ++i) ans.push_back(points[i]);
		return ans;
	}
};

本代码提交AC,用时612MS。

LeetCode Can Make Arithmetic Progression From Sequence

5452. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6

给一个数组,问能否通过排列组合让这个数组变成等差数列。

直接排序,看看是否是等差数列即可:

class Solution {
public:
	bool canMakeArithmeticProgression(vector<int>& arr) {
		sort(arr.begin(), arr.end());
		int diff = arr[1] - arr[0];
		for (int i = 2; i < arr.size(); ++i) {
			if (arr[i] - arr[i - 1] != diff)return false;
		}
		return true;
	}
};

本代码提交AC。

LeetCode Diagonal Traverse II

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= nums[i][j] <= 10^9
  • There at most 10^5 elements in nums.

如上图所示,给定一个残缺矩阵,要求遍历每个对角线,输出所有元素的值。

朴素解法会TLE,特别是如果有某一行或某一列比其他行列长特别多的情况。

提示解法:观察规律发现,处于同一对角线的元素的行列下标之和相等。所以我们可以把所有元素的行列下标进行排序,如果下标和相等,则处于同一对角线,按行下标从大到小排序;如果下标和不相等,则按下标和从小到大排序。完整代码如下:

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
	int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
	if (sum1 == sum2) {
		return p1.first > p2.first;
	}
	else {
		return sum1 < sum2;
	}
}
class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
		vector<pair<int, int>> idxs;
		for (int i = 0; i < nums.size(); ++i) {
			for (int j = 0; j < nums[i].size(); ++j) {
				idxs.push_back(make_pair(i, j));
			}
		}
		sort(idxs.begin(), idxs.end(), cmp);
		vector<int> ans;
		for (int i = 0; i < idxs.size(); ++i) {
			ans.push_back(nums[idxs[i].first][idxs[i].second]);
		}
		return ans;
	}
};

本代码提交AC,用时500MS。

LeetCode Maximum Performance of a Team

1383. Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers. 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

给定n个工程师,每个工程师有自己的速度值speed和效率值efficiency,一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率:sum(speed)*min(efficiency)。问最多选k个工程师,最大的performance是多少。

我一开始被“最多k个”迷惑了,一直以为是一个DP题,后来看题解发现不是。

由于performance=sum(speed)*min(efficiency),所以首先对n个工程师按efficiency从大到小排序,然后对于前m个工程师,他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k,则需要从m个工程师中剔除掉速度最小的工程师,因为此时的min(efficiency)固定是第m个工程师的efficiency,所以只需要剔除速度低的工程师。

那么,如果最优解是少于k个人,这种方法能否找到最优解呢?其实是可以的,因为对于每加入一个工程师,我们都会和当前最优解对比,刚开始的时候,队列中的人数肯定少于k。

完整代码如下:

class Solution {
public:
	int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
		vector<pair<int, int>> workers;
		for (int i = 0; i < n; ++i) {
			workers.push_back(make_pair(efficiency[i], speed[i]));
		}
		sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
		priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆,这是构建最小堆
		long long ans = 0;
		long long sum_speed = 0;
		for (int i = n - 1; i >= 0; --i) {
			sum_speed += workers[i].second;
			pq.push(workers[i].second);
			if (pq.size() > k) {
				sum_speed -= pq.top();
				pq.pop();
			}
			ans = max(ans, sum_speed*workers[i].first);
		}
		return ans % (int)(1e9 + 7);
	}
};

本代码提交AC,用时108MS。

LeetCode Rank Teams by Votes

1366. Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

  • 1 <= votes.length <= 1000
  • 1 <= votes[i].length <= 26
  • votes[i].length == votes[j].length for 0 <= i, j < votes.length.
  • votes[i][j] is an English upper-case letter.
  • All characters of votes[i] are unique.
  • All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

给定很多人对很多team的打分排序列表,如果一个队排在前面的名次越多,则其最终名次越高,据此输出最终排序列表。

规则很复杂,其实很简单。设计一个Team的类,它有一个scores数组,scores[i]表示这个队被多少人投票排在了第i名。由于最多只有26个队,所以scores的维度为26。对Team自定义排序函数,排序规则是依次比较scores的每个元素大小,如果都相等的话,最后比较name的大小。

完整代码如下:

const int MAXN = 26;
class Team {
public:
	char name;
	vector<int> scores;

	Team() :name(0) {
		scores.resize(MAXN, 0);
	};

	bool operator<(const Team& t) {
		for (int i = 0; i < MAXN; ++i) {
			if (scores[i] > t.scores[i]) {
				return true;
			}
			else if (scores[i] < t.scores[i]) {
				return false;
			}
		}
		return name < t.name;
	}
};

class Solution {
public:
	string rankTeams(vector<string>& votes) {
		vector<Team> teams(MAXN, Team());
		for (int j = 0; j < votes[0].size(); ++j) {
			int idx = votes[0][j] - 'A';
			teams[idx].name = votes[0][j]; // 出现的team name
		}
		for (int i = 0; i < votes.size();++i) {
			for (int j = 0; j < votes[i].size(); ++j) {
				int idx = votes[i][j] - 'A';
				++teams[idx].scores[j];
			}
		}
		vector<Team> showups;
		for (int i = 0; i < MAXN; ++i) {
			if (teams[i].name != 0) {
				showups.push_back(teams[i]);
			}
		}
		sort(showups.begin(), showups.end());
		string ans = "";
		for (int i = 0; i < showups.size(); ++i) {
			ans += showups[i].name;
		}
		return ans;
	}
};

本代码提交AC,用时20MS。

LeetCode Find K Closest Elements

LeetCode Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

给定一个有序数组,要从中找出k个和x最接近的元素,按升序排列输出。 首先在有序数组中用二分查找找到x的lowerbound,如果lowerbound指向begin(),则取开头k个元素即可;如果lowerbound指向end(),则取末尾k个元素;否则,令left指向lowerbound-1,right指向lowerbound,每次取left、right中和x差值最小的那个数,直到取够k个为止。最后对结果数组排序。 完整代码如下: [cpp] class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { vector<int> ans; int n = arr.size(); auto it = lower_bound(arr.begin(), arr.end(), x); if (it == arr.begin()) { while (ans.size() < k) { ans.push_back(*it++); } return ans; } else if (it == arr.end()) { while (ans.size() < k) { ans.push_back(*–it); } return ans; } else { int right = it – arr.begin(); int left = right – 1; int left_diff = INT_MAX, right_diff = INT_MAX; while (ans.size() < k) { if (left >= 0)left_diff = abs(arr[left] – x); else left_diff = INT_MAX; if (right < n)right_diff = abs(arr[right] – x); else right_diff = INT_MAX; if (left_diff <= right_diff) { ans.push_back(arr[left]); –left; } else { ans.push_back(arr[right]); ++right; } } } sort(ans.begin(), ans.end()); return ans; } }; [/cpp] 本代码提交AC,用时143MS。]]>

LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order. Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
  1. The number of given pairs will be in the range [1, 1000].

如果两个数对(a,b)和(c,d)满足b<c,则(c,d)可以跟在(a,b)的后面。给定一系列数对(s,t),问从这些数对中最多能取出多少个数对满足连续满足这种条件。 解法1,使用DP。首先对所有数对(x,y)先按x排序,x相同再按y排序。然后遍历数对,对于每个数对,有两种选择,不要或者要,对应dp[i][0]和dp[i][1],表示到i时能选出来的最多的满足条件的数对。 则dp[i][0]=max(dp[i-1][0], dp[i-1][1]),因为第i个数对不选,所以肯定等于前i-1个能选出来的最大数对,也就是max(dp[i-1][0], dp[i-1][1])。 如果第i个数对选,则要往前找到一个和i不冲突的数对j,接在j的后面,所以dp[i][1]=dp[j][1]+1。 代码如下: [cpp] bool cmp(const vector<int>& p1, const vector<int>& p2) { return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); } class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), cmp); int n = pairs.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = 1; int ans = 1; for (int i = 1; i < n; ++i) { dp[i][0] = max(dp[i – 1][0], dp[i – 1][1]); dp[i][1] = 1; int j = i – 1; while (j >= 0 && pairs[i][0] <= pairs[j][1]) { –j; } if (j >= 0) { dp[i][1] = max(dp[i][1], dp[j][1] + 1); } ans = max(ans, dp[i][0]); ans = max(ans, dp[i][1]); } return ans; } }; [/cpp] 本代码提交AC,用时49MS。 我隐隐觉得这种解法有问题,就是在求dp[i][1]的时候,应该要找i前面所有和i不冲突的j,求max,即dp[i][1]=max(dp[j][1]+1)。 所以解法2是无懈可击的DP解法。设dp[i]表示以数对i结尾能得到的最长的链式数对,则初始的时候,所有dp[i]=1。然后对于第i个数对,遍历i前面所有数对j,只要i和j能够链起来,则求dp[i]=max(dp[j]+1)。时间复杂度$$O(n^2)$$,代码如下: [cpp] class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); }); int n = pairs.size(), ans = 1; vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = i – 1; j >= 0; –j) { if (pairs[i][0] > pairs[j][1]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; } }; [/cpp] 本代码提交AC,用时122MS。 解法3,首先还是对所有数对排序,然后把这题看成类似于求最长上升子序列。即设dp[k]=构成链条长度为k时最小的结束时间。那么来了一个数对之后,如果该数对的开始时间大于dp末尾的结束时间,则说明该数对可以追加到dp中,链条长度加1,dp[k+1]=该数对的结束时间。否则,如果该数对的开始时间不大于dp末尾的结束时间,则需要像LIS一样,把该数对插入到dp中,因为dp是排好序的,所以二分插入即可。 该思路请参考:https://discuss.leetcode.com/topic/96814/python-straightforward-with-explanation-n-log-n/2。比较有意思的是,正如第一个评论人所说,因为提前对数对按结束时间排序了,所以后面的数对肯定是大于等于dp末尾的数对的,所以新来的数对只可能追加到dp的末尾,不可能插入到dp的其他位置,所以就可以省略二分插入的过程。完整代码简洁如下: [cpp] class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; }); int ans = 0; for (int i = 0, j = 0; j < pairs.size(); ++j) { if (j == 0 || pairs[j][0] > pairs[i][1]) { ++ans; i = j; } } return ans; } }; [/cpp] 本代码提交AC,用时45MS。 这个题可以把每个数对看成一个活动的开始和结束时间,把问题转换为从所有活动中选出尽量多的不重叠的活动,求最多的活动个数。活动选择问题可以用贪心求解,详细介绍和证明请看维基百科。]]>

LeetCode Design Log Storage System

LeetCode Design Log Storage System You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers. Design a log storage system to implement the following functions: void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system. int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017. Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.
Note:
  1. There will be at most 300 operations of Put or Retrieve.
  2. Year ranges from [2000,2017]. Hour ranges from [00,23].
  3. Output for Retrieve has no order required.

设计一个日志系统,该系统有两个操作,put(id,timestamp)把timestamp时刻的日志id放到日志系统中,retrieve(start,end,gra)从系统中取出timestamp范围在[start,end]之间的日志id,时间的粒度是gra。 我设计的系统是这样的,为了方便retrieve,系统中的日志都按timestamp排序了。有趣的是,在zero-padded(每部分不足补前导0)的情况下,timestamp的字符串排序就是timestamp表示的时间的排序。 定义一个Node结构体,保持一个日志,信息包括日志id和timestamp。用一个链表存储所有Node,并且当新Node插入时,采用插入排序的方法使得链表始终有序。 retrieve的时候,根据粒度,重新设置start和end,比如样例中粒度为Year时,把start改为Year固定,其他时间最小
"2016:00:00:00:00:00"
把end改为Year固定,其他时间最大
"2017:12:31:23:59:59"
这样我只需要遍历链表,把所有timestamp字符串在这个范围内的日志id取出来就好了。其他粒度也是类似的。 完整代码如下: [cpp] class LogSystem { private: struct Node { int id; string timestamp; Node(int i, string t) :id(i), timestamp(t) {}; }; list<Node> log; string start, end; public: LogSystem() { start = "2000:00:00:00:00:00"; end = "2017:12:31:23:59:59"; } void put(int id, string timestamp) { Node node(id, timestamp); if (log.empty())log.push_back(node); else { auto it = log.begin(); while (it != log.end() && (*it).timestamp <= timestamp)++it; log.insert(it, node); } } vector<int> retrieve(string s, string e, string gra) { if (gra == "Year") { s = s.substr(0, 4) + start.substr(4); e = e.substr(0, 4) + end.substr(4); } else if (gra == "Month") { s = s.substr(0, 7) + start.substr(7); e = e.substr(0, 7) + end.substr(7); } else if (gra == "Day") { s = s.substr(0, 10) + start.substr(10); e = e.substr(0, 10) + end.substr(10); } else if (gra == "Hour") { s = s.substr(0, 13) + start.substr(13); e = e.substr(0, 13) + end.substr(13); } else if (gra == "Minute") { s = s.substr(0, 16) + start.substr(16); e = e.substr(0, 16) + end.substr(16); } vector<int> ans; auto it = log.begin(); while (it != log.end() && (*it).timestamp < s)++it; while (it != log.end() && (*it).timestamp <= e) { ans.push_back((*it).id); ++it; } return ans; } }; [/cpp] 本代码提交AC,用时19MS。]]>

LeetCode Wiggle Sort II

LeetCode Wiggle Sort II Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2]. Note: You may assume all input has valid answer. Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?


给定一个数组,对其进行wiggle排序,如果下标从0开始,则奇数下标的数都要大于其相邻两个数,即nums[0] < nums[1] > nums[2] < nums[3]…. 普通解法是这样的,先给数组排序,然后设置首尾指针,分别取较小的数放到偶数位,较大的数放到奇数位。比如第一个样例排序之后是[1,1,1,4,5,6],i指向1,j指向6,开辟一个新数组,依次把nums[i++]和nums[j–]放到新数组中,形成[1,6,1,5,1,4],满足要求。 但是有一种情况会出问题,比如[4,5,5,6],按上面的方法,得到的数组是[4,6,5,5],最后的5,5不满足要求,究其原因,是因为随着i和j的推进,他们指向的数的差值越来越小,导致最后可能出现相等的情况。遇到这种情况,我们可以设置i从mid开始取,j从n-1开始取,这样i和j指向的数的差值始终是很大的,这样得到的结果就是[5,6,4,5] 因为题目说每个样例都有解,而wiggle sort的结果是先小后大,所以小数的个数总是大于等于大数的个数,比如1,2,1小数的个数大于大数的个数,1,2,1,2小数的个数等于大数的个数。所以我们i从mid开始时,如果数组有偶数个数,则中位数有两个,我们的mid应该是前一个中位数,这样能保证小数个数等于大数个数;如果数组有奇数个数,则中位数只有一个,我们的mid就从这个中位数开始,这样小数个数比大数个数多1。 所以第一个版本我们可以 [cpp] class Solution { private: //自己实现的快排程序 void my_quick_sort(vector<int>& nums, int s, int t) { int i = s, j = t, pivot = s; if (i >= j)return; while (i <= j) { while (i <= j&&nums[i] <= nums[pivot])++i; if (i > j)break; while (i <= j&&nums[j] >= nums[pivot])–j; if (i > j)break; swap(nums[i++], nums[j–]); } swap(nums[pivot], nums[j]); my_quick_sort(nums, s, j – 1); my_quick_sort(nums, j + 1, t); } public: void wiggleSort(vector<int>& nums) { int n = nums.size(); my_quick_sort(nums, 0, n – 1); int i = (n & 1) == 0 ? n / 2 – 1 : n / 2, j = n – 1; vector<int> ans(n, 0); for (int k = 0; k < n; ++k) { ans[k] = (k & 1) == 0 ? nums[i–] : nums[j–]; } nums = ans; } }; [/cpp] 手工写了快排程序,并手工根据n的奇偶性对i赋不同的值。本代码提交AC,用时569MS。自己写的快排是有多慢呀。 我们也可以这样 [cpp] class Solution { public: void wiggleSort(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(), i = (n + 1) / 2, j = n; vector<int> ans(n, 0); for (int k = 0; k < n; ++k) { ans[k] = (k & 1) == 0 ? nums[–i] : nums[–j]; } nums = ans; } }; [/cpp] 使用库中的sort,并且(n+1)/2相当于得到了偶数长的较大的中位数,或者奇数长中位数的下一个数,为了校准,进行了–i处理。本代码提交AC,用时86MS。 讨论区还有O(n)时间O(1)空间的解法,下回再战。]]>

LeetCode K-diff Pairs in an Array

LeetCode K-diff Pairs in an Array Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won’t exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

给定一个数组,问数组中绝对差值为k的unique数对有多少个。 注意数对不能有重复,比如第一个样例,虽然有两个1,但是2-diff的数对(1,3)只能算一个。 我使用的方法非常简单直白。首先因为绝对误差肯定是非负数,所以如果k<0,则直接返回0对。 然后如果k==0,则说明数对中的两个数必须相等,所以对于k==0的情况,只需要统计一下数组中有多少个重复的数。 如果k>0,则对于每一个数num,如果num+k也在数组中,则找到一个k-diff的数对。 所以为了方便查找和统计,我们首先把数和频率统计到一个map中,边map,可以边统计重复数字个数repeated。 如果k==0,直接返回repeated。 否则把map的key放到一个新的vector中,根据map的性质,这个新的vector是sorted的。则遍历sorted数组,判断每个num+k是否在map中,在则++ans。最后返回ans。 完整代码如下: [cpp] class Solution { public: int findPairs(vector<int>& nums, int k) { if (k < 0)return 0; int repeated = 0; map<int, int> count; for (const auto& num : nums) { ++count[num]; if (count[num] == 2)++repeated; } if (k == 0)return repeated; vector<int> sorted; for (const auto& it : count) { sorted.push_back(it.first); } int ans = 0; for (const auto& num : sorted) { if (count.find(num + k) != count.end())++ans; } return ans; } }; [/cpp] 本代码提交AC,用时48MS。]]>