题解 | #合法的三角形个数#

合法的三角形个数

http://www.nowcoder.com/practice/e6ee5545535445feaeb92f357644fb14

该题的解法如下:
首先,对各边长进行排序,方便获取三边中最长的边。
然后,进入循环,循环体如下:
由小到大找最长边(循环)
从最长边开由大到小找次长边(循环)
从次长边开始由大到小找最短边。(循环计数法,或者用二分查找法找上界,然后用计算中间个数)

        //循环计数法
	int validTriangleNumber1(vector<int>& nums) 
	{
		int length = nums.size();
		if (length < 3) return 0;
		sort(nums.begin(), nums.end());//排序
		int res = 0;
		for (int right = 2; right < length; ++right)//right最长边序号
		{
			for (int mid = right - 1; mid > 0; --mid)//mid次长边序号
			{
				int temp = nums[right] - nums[mid];//找出最短边的最短长度temp
                                if (temp > nums[mid]) break;//如果最短边长度的最短长度已经比次长长,打断循环
				for (int left = mid - 1; left >=0 ; --left) //left最短边序号
                                {
					if (nums[left] <= temp)
						break;
					++res;//计数
				}
			}
		}
		return res;
	}

	//二分查找上界法
        int validTriangleNumber(vector<int>& nums)
	{
		int length = nums.size();
		if (length < 3) return 0;
		sort(nums.begin(), nums.end());//排序
                int res = 0;
		for (int right = 2; right < length; ++right)//right最长边序号
		{
			for (int mid = right - 1; mid > 0; --mid)//mid次长边序号
			{
				int temp = nums[right] - nums[mid];//找出最短边的最短长度temp
				if (temp > nums[mid]) break;//如果最短边长度的最短长度已经比次长长,打断循环
				auto bg = nums.begin();
				auto upperBound = upper_bound(bg, bg + mid, temp);//利用二分法找出最短边长度上界
				res += mid - (upperBound - bg);//计算中间边的个数
			}
		}
		return res;
	}



全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
05-16 21:14
中南大学 Java
白火同学:说到底就是无实习的秋招、有实习的春招,哪个更难找到工作嘛。 现在离秋招还有两个半月时间,你现在可以一边背八股刷算法,一边投实习简历,看能不能拿到一份7-9月的实习。你这9本和技术栈找实习是够的,那你实习过程中继续优化简历。9月一边实习一边继续投秋招简历。
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务