首页 > 代码库 > leetcode-6-basic
leetcode-6-basic
解题思路:
这道题真实地反映了我今晚有多脑残=。=只需要从根号N开始向前找,第一个能被N整除的数就是width,然后存到结果就
可以了。因为离根号N越近,width越大,与length的差越小。
vector<int> constructRectangle(int area) { vector<int> result; int i; //float min = 0.1; int length,width; int start = pow(area, 0.5); for (i = start; i >= 1; i--) { if (area % i == 0) { width = i; length = area / i; break; } } result.push_back(length); result.push_back(width); return result; }
解题思路:这道题要求运行时间为O(n)且不能有额外的空间,有点意思。不过题目限定数组里都是正整数,且刚好在[1,size]
的范围内,所以考虑用负号做区分。从头开始扫描,将nums[nums[i]-1]的值设为负数,那么等扫描过一遍之后,
仍然是正数的index再加1就是缺失的数了。需要注意的是,设负数后,index会有负数,所以应该是将nums[abs(nums[i]) - 1]
设为负数。
vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> result; int i; for (i = 0; i < nums.size(); i++) { if (nums[abs(nums[i])-1] > 0) nums[abs(nums[i])-1] *= -1; } for (i = 0; i < nums.size(); i++) { if (nums[i] > 0) result.push_back(i+1); } return result; }
leetcode-6-basic
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。