Tag Archives: 排序

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个为止。最后对结果数组排序。
完整代码如下:

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;
	}
};

本代码提交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。
代码如下:

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;
	}
};

本代码提交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),代码如下:

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;
	}
};

本代码提交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的其他位置,所以就可以省略二分插入的过程。完整代码简洁如下:

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;
	}
};

本代码提交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取出来就好了。其他粒度也是类似的。
完整代码如下:

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;
	}
};

本代码提交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。
所以第一个版本我们可以

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;
	}
};

手工写了快排程序,并手工根据n的奇偶性对i赋不同的值。本代码提交AC,用时569MS。自己写的快排是有多慢呀。
我们也可以这样

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;
	}
};

使用库中的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。
完整代码如下:

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;
	}
};

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

LeetCode Course Schedule III

LeetCode Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

  1. The integer 1 <= d, t, n <= 10,000.
  2. You can't take two courses simultaneously.

给定一系列课程,每门课有持续时间以及该课程关闭时间。从0时刻开始,问最多能完成多少门课程。注意不能同时上多门课程。
使用贪心的思路, 首先根据经验,越早结束的课程,越早选修并结束该课程越好,因为这样可以留出更多的时间选修其他课程。所以我们首先对所有课程按关闭时间从小到大排序,每次我们贪心的选择最早关闭的课程。
如果now+duration<=closed,即当前时间加该课程的持续时间不超过课程的关闭时间,则贪心选修该课程,并且把该课程的持续时间插入到一个优先队列中(最大堆)。
如果不能选修该课程,且优先队列中堆顶的持续时间比当前课程还大,则可以把堆顶课程删掉,换成该门课程,这样该门课程肯定可以选修并完成,同时使得新的now比之前的now要小,更有利于选修更多的课程。
举个例子,假设已经按关闭时间排序了[3,8],[7,10],[5,14],[8,17],now=0。

  1. 选修第一门课程,now=3<8,优先队列堆顶为3
  2. 选修第二门课程,now=3+7=10<=10,优先队列堆顶为7
  3. 选修第三门课程,now=10+5=15>14,失败;发现堆顶课程的持续时间是7,大于当前课程的持续时间5,所以可以把堆顶课程换成该门课程,则新的now=10-7+5=8,堆顶为5。因为该门课程的持续时间比堆顶短,且关闭时间已排序,所以大于堆顶的关闭时间,所以把堆顶课程换成该课程,该课程肯定能过完成。且新的now=8比先前的now=10要小,使得可以完成第四门课程。
  4. 选修第四门课,now=8+8=16<17,优先队列为8。

完整代码如下:

class Solution {
public:
	int scheduleCourse(vector<vector<int>>& courses) {
		auto cmp = [](vector<int>& c1, vector<int>& c2) {return c1[1] < c2[1]; };
		sort(courses.begin(), courses.end(), cmp);
		int now = 0, ans = 0;
		priority_queue<int> pq;
		for (const auto& c : courses) {
			if (now + c[0] <= c[1]) {
				++ans;
				now += c[0];
				pq.push(c[0]);
			}
			else if (!pq.empty() && c[0] < pq.top()) {
				now = now - pq.top() + c[0];
				pq.pop();
				pq.push(c[0]);
			}
		}
		return ans;
	}
};

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

LeetCode Maximum Product of Three Numbers

LeetCode Maximum Product of Three Numbers
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

给定一个整数数组,选出三个数,使得乘积最大。
整数数组中可能有负数,所以我们先对数组从小到大排序。如果最小值都大于0,说明没有负数,则三数乘积最大就是最大的前3个数的乘积。
如果有负数,且至少有两个负数,则还需要判断一下最小的两个负数乘以最大的正数的乘积,这个数和前一种情况的大小关系。
代码如下:

class Solution {
public:
	int maximumProduct(vector<int>& nums) {
		int n = nums.size();
		sort(nums.begin(), nums.end());
		int ans1 = nums[n - 1] * nums[n - 2] * nums[n - 3], ans2 = 0;
		if (nums[0] > 0)return ans1;
		if (nums[0] < 0 && nums[1] < 0)ans2 = nums[0] * nums[1] * nums[n - 1];
		return max(ans1, ans2);
	}
};

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

LeetCode Maximum Distance in Arrays

LeetCode Maximum Distance in Arrays
Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
Example 1:

Input:
[[1,2,3],
 [4,5],
 [1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

  1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
  2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
  3. The integers in the m arrays will be in the range of [-10000, 10000].

给定m个已从小到大排序的数组,要求从两个不同的数组中取出两个数,使得这两个数的差的绝对值最大,问最大的差的绝对值是多少。
因为数组已排序,所以最大的差值肯定等于某个数组的最大值和另一个数组的最小值的差。这里唯一需要注意的是两个数必须选自两个不同的数组。
我开始的做法是这样的,把所有数组的最大值和最小值都拿出来,然后重新排个序。在新数组中,如果最大值和最小值来自不同的数组,则他们的差就是最终结果。加入最大值和最小值是来自同一个数组的,则求最大值和次小值的差以及次大值和最小值的差中的最大值。因为最大值和最小值来自同一个数组,所以最大值和次小值以及次大值和最小值肯定不是来自同一个数组的。
代码如下:

class Solution {
	struct P {
		int idx;
		int value;
		P(int i, int v) :idx(i), value(v) {};
		bool operator<(const P& p) {
			return this->value < p.value;
		}
	};
public:
	int maxDistance(vector<vector<int>>& arrays) {
		vector<P> vp;
		for (int i = 0; i < arrays.size(); ++i) {
			vp.push_back({ i,arrays[i][0] });
			vp.push_back({ i,arrays[i][arrays[i].size() - 1] });
		}
		sort(vp.begin(), vp.end());
		int ans = 0, n = vp.size();
		if (vp[0].idx != vp[n - 1].idx)return abs(vp[n - 1].value - vp[0].value);
		return max(abs(vp[n - 1].value - vp[1].value), abs(vp[n - 2].value - vp[0].value));
	}
};

本代码提交AC,用时26MS。因为要对m个数组的最大值和最小值排序,所以时间复杂度为O((2m)lg(2m))。
讨论区还有一种解法,只需要O(m)的复杂度。我们遍历每个数组,记录之前所有数组的最小值的最小值以及最大值的最大值,然后用当前数组的最大值和最小值减去之前所有数组中的最小值的最小值以及最大值的最大值,求绝对值,更新结果。这样就作差的两个数肯定来自不同的数组,避免了之前的问题。
代码如下:

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int ans = INT_MIN;
        int curMin = arrays[0][0], curMax = arrays[0][arrays[0].size() - 1];
        for(int i = 1; i < arrays.size(); ++i) {
            ans = max(ans, abs(arrays[i][0] - curMax));
            ans = max(ans, abs(arrays[i][arrays[i].size() - 1] - curMin));
            curMin = min(curMin, arrays[i][0]);
            curMax = max(curMax, arrays[i][arrays[i].size() - 1]);
        }
        return ans;
    }
};

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

LeetCode Shortest Unsorted Continuous Subarray

LeetCode Shortest Unsorted Continuous Subarray
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

给定一个数组,问最短对多长的子数组排序之后,整个数组都会是升序的。比如样例对中间的[6,4,8,10,9]这个子数组排序之后,放回到原数组,原数组也是升序排列的。
第一种解法是,直接对数组排序,然后把已排序数组和未排序数组分别从首位对比,遇到第一个不相等的位置就跳出,然后需要排序的子数组长度就是j-i+1了。
代码如下:

class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		vector<int> nums_copy = nums;
		sort(nums_copy.begin(), nums_copy.end());
		int i = 0, j = nums.size() - 1;
		while (i <= j&&nums[i] == nums_copy[i])++i;
		while (j >= i&&nums[j] == nums_copy[j])--j;
		return j - i + 1;
	}
};

本代码提交AC,用时52MS,时间复杂度是O(nlgn)。
还有一种O(n)的方法,参考这个题解
基本思想是这样:

  1. 从左往右,如果该数已经在最终排序的位置了,那么该数必须小于等于该数右边的最小值
  2. 从右往左,如果该数已经在最终排序的位置了,那么该数必须大于等于该数左边的最大值

如果违反1,那么该数右边还有比该数小的数,所以需要把这个更小的数放到该数前面,也就是说该数不在其最终的位置;违反2也是类似的。
所以我们维护两个数组,分别存储从左往右的最大值和从右往左的最小值,然后和原数组比较即可。
代码如下:

/**
 *            /------------\
 * nums:  [2, 6, 4, 8, 10, 9, 15]
 * minsf:  2  4  4  8   9  9  15
 *         <--------------------
 * maxsf:  2  6  6  8  10 10  15
 *         -------------------->
 */
class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		int n = nums.size();
		vector<int> min_so_far(n, 0), max_so_far(n, 0);
		for (int i = 0, maxsf = INT_MIN; i < n; ++i)max_so_far[i] = maxsf = max(maxsf, nums[i]);
		for (int i = n - 1, minsf = INT_MAX; i >= 0; --i)min_so_far[i] = minsf = min(minsf, nums[i]);
		int i = 0, j = n - 1;
		while (i <= j&&nums[i] <= min_so_far[i])++i;
		while (j >= i&&nums[j] >= max_so_far[j])--j;
		return j - i + 1;
	}
};

本代码提交AC,用时72MS,时间复杂度是O(n),但是为啥比第一种方法还慢呀。

LeetCode Heaters

LeetCode Heaters
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters' warm radius range, it can be warmed.
  4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

给定房子和加热器的位置,问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆,所有加热器的加热半径都是一样的。
要保证每个房子都在加热范围之内,且加热器的半径最小,则房子i肯定被紧邻i前后的两个加热器之一覆盖,其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y,i表示房子坐标,x和y分别表示紧邻i的两个加热器坐标,则覆盖i的最小半径应该是min(i-x,y-i)。
所以问题就转换为对每个房子坐标i,去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y,然后根据上述公式更新结果。为了便于查找,先对加热器坐标排序,然后直接二分查找就好了。
代码如下:

class Solution {
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0;
		for (int i = 0; i < houses.size(); ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			auto lb = lower_bound(heaters.begin(), heaters.end(), pos);
			if (lb > heaters.begin())r = min(r, pos - *(lb - 1));
			auto ub = lower_bound(heaters.begin(), heaters.end(), pos);
			if (ub < heaters.end())r = min(r, *ub - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

本代码提交AC,用时89MS。
还可以自己写二分查找代码,如下:

class Solution {
private:
	int my_lower_bound(vector<int>& v, int target) {
		int l = 0, r = v.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (target > v[m])l = m + 1;
			else r = m - 1;
		}
		return l;
	}
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0, n = houses.size(), m = heaters.size();
		for (int i = 0; i < n; ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			int lb = my_lower_bound(heaters, pos);
			if (lb > 0)r = min(r, pos - heaters[lb - 1]);
			if (lb < m)r = min(r, heaters[lb] - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

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