[LeetCode]Next Closest Time

找字典序大于当前时间最小时间，只需要从LSB(least significant bit)开始，对处于每一位的digit d，找到大于d的最小的合法的数字，如果找不到赋予当前位4个位当中的最小数即可。因为最小的数一定可以保证小于等于2(最左边的位)，所以只要输入是合法的，我们永远可以找到一个合法的解。常数时间和空间，代码如下：

	class Solution {
	public:
	string nextClosestTime(string time) {
	vector<int> digits;
	for (const auto c : time)
	{
	if (isdigit(c))
	digits.push_back(c - '0');
	}
	sort(digits.begin(), digits.end());
	for (int i = 4; i >= 0; --i)
	{
	if (i == 2)continue;
	int digit = time[i] - '0', idx = findNextGreater(digits, digit);
	if (idx == -1 || !isValid(i, digits[idx], time))
	time[i] = '0' + digits[0];
	else
	{
	time[i] = '0' + digits[idx];
	break;
	}
	}
	return time;
	}
	private:
	int findNextGreater(vector<int>& nums, int curr)
	{
	int len = nums.size(), lo = 0, hi = len - 1;
	while (lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	if (nums[mid] <= curr)lo = mid + 1;
	else hi = mid - 1;
	}
	return lo >= len? -1 : lo;
	}
	bool isValid(int pos, int digit, const string& time)
	{
	if (pos == 0)return digit <= 2;
	else if (pos == 1)return time[0] == '2'? digit <= 3: digit <= 9;
	else if (pos == 3)return digit <= 5;
	else if (pos == 4)return digit <= 9;
	else return false;
	}
	};

view raw Next Closest Time.cpp hosted with ❤ by GitHub