本文涉及的基础知识点

C++二分查找

LeetCode825. 适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。
注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1：
输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。
示例 2：
输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：
n == ages.length
1 <= n <= 2 * 10⁴
1 <= ages[i] <= 120

二分查找

如果条件三成立，则条件二一定成立，故条件三是多余的。
同时满足以下两个条件则发送：
条件四：ages[y] > 0.5*ages[x]+7
条件五：ages[y] <= ages[x]
条件四简化后：2$\times$ages[y] > ages[x]+14 即 ages[x] < 2$\times$ages[y]-14
联合后，条件六：ages[y] <= arges[x] < 2$\times$ages[y]-14
向对ages排序，枚举ages[y]，统计符合条件的ages[x]。由于ages[y]可能符合要求：ages[y] <2ages[y]-14 。如果此不等式成立，则ages[y]也是解，需要扣掉。如果此不等式不成立，则无解。

代码

核心代码

class Solution {
		public:
			int numFriendRequests(vector<int>& ages) {
				sort(ages.begin(), ages.end());
				int ret = 0;
				for (const auto& n : ages) {
					if (n >= 2* n - 14) { continue; }
					auto it1 = lower_bound(ages.begin(), ages.end(), n);
					auto it2 = lower_bound(ages.begin(), ages.end(), 2*n-14);
					ret += it2 - it1;		
					ret--;	
				}
				return ret ;
			}
			
		};

单元测试用例

TEST_CLASS(LeetCode825)
	{
		//LeetCode825. 适龄的朋友
		class Solution {
		public:
			int numFriendRequests(vector<int>& ages) {
				sort(ages.begin(), ages.end());
				int ret = 0;
				for (const auto& n : ages) {
					if (n >= 2* n - 14) { continue; }
					auto it1 = lower_bound(ages.begin(), ages.end(), n);
					auto it2 = lower_bound(ages.begin(), ages.end(), 2*n-14);
					ret += it2 - it1;		
					ret--;	
				}
				return ret ;
			}
			int Test(vector<int>& ages) {
				int ret = 0;
				sort(ages.begin(), ages.end());
				for (int y = 0; y < ages.size(); y++) {
					Logger::WriteMessage(("\r\n" + std::to_string(ages[y])+"\r\n").c_str());
					for (int x = 0; x < ages.size(); x++) {
						if (y == x) { continue; }
						if (ages[y] <= 0.5 * ages[x] + 7) { continue; }
						if (ages[y] > ages[x]) { continue; }
						ret++;
						Logger::WriteMessage((" " + std::to_string(ages[x])).c_str());
					}
				}
				return ret;
			}
		};
	public:
		vector<int> ages;
		TEST_METHOD(TestMethod1)
		{
			ages = { 5 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod2)
		{
			ages = { 20 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod3)
		{
			ages = { 11,12 };
			auto res1 = Solution().Test(ages);
			auto res = Solution().numFriendRequests(ages);
			AssertEx(res1, res);
		}
		TEST_METHOD(TestMethod11)
		{
			ages = { 16, 16 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			ages = { 16, 17,18 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			ages = { 20,30,100,110,120 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod14)
		{
			ages = { 108,115,5,24,82 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod15)
		{
			ages = { 101,98,80,20,1,97,3,77,114,109 };			
			auto res1 = Solution().Test(ages);
			auto res = Solution().numFriendRequests(ages);
			AssertEx(res1, res);
		}
	};