2017-3-10 leetcode 229 238 268

今天登陆leetcode突然发现531被锁了，有种占了便宜的感觉哈哈哈！

================================================

leetcode229 Majority Element II

leetcode238 Product of Array Except Self

================================================

229讲的是
给你n个数字，找出所有出现次数超过n/3的数字，要求O(n)time O(1)space
这道题简化版是 leetcode169 解法见2017-3-6

我的思路
类似169，只不过这次因为总数大于[n/3]，要维护两个候选数字（最多有两个元素符合要求），每次有新的数字出现的时候，两个计数器都要减。扫一遍得到两个候选数字后，再扫一遍确认数目是否符合要求。

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4         int n=nums.size();
 5         int num1=-1,num2=-1,cnt1=0,cnt2=0;
 6         for(int i=0;i<n;i++){
 7             if(num1==nums[i]){
 8                 cnt1++;
 9             }else if(num2==nums[i]){
10                 cnt2++;
11             }else if(!cnt1){
12                 cnt1++;num1=nums[i];
13             }else if(!cnt2){
14                 cnt2++;num2=nums[i];
15             }else{
16                 cnt1--;cnt2--;
17             }
18         }
19         cnt1=cnt2=0;
20         for(int i=0;i<n;i++){
21             if(nums[i]==num1)cnt1++;
22             if(nums[i]==num2)cnt2++;
23         }
24         vector<int> aim;
25         if(cnt1>n/3)aim.push_back(num1);
26         if(cnt2>n/3)aim.push_back(num2);
27         return aim;
28     }
29 };

229

238讲的是
给你一个n个数的数组nums[i]，输出一个n个数的数组output[i]=nums的累乘/nums[i]。要求不能使用除法，O(n)time

我的思路
求个前缀乘，求个后缀乘，然后乘在一起？？？？？

1 class Solution { 2 public: 3 vector<int> productExceptSelf(vector<int>& nums) { 4 int n=nums.size(); 5 vector<int> pre_pro(n,1),suf_pro(n,1),output(n); 6 for(int i=n-2;i>-1;i--){ 7 suf_pro[i]=suf_pro[i+1]*nums[i+1]; 8 } 9 output[0]=suf_pro[0]; 10 for(int i=1;i<n;i++){ 11 pre_pro[i]=pre_pro[i-1]*nums[i-1]; 12 output[i]=suf_pro[i]*pre_pro[i]; 13 } 14 return output; 15 } 16 };

1 class Solution { 2 public: 3 vector<int> productExceptSelf(vector<int>& nums) { 4 int n=nums.size(); 5 int pre_pro=1,suf_pro=1; 6 vector<int> output(n,1); 7 for(int i=0;i<n;i++){ 8 output[i]*=pre_pro; 9 pre_pro*=nums[i]; 10 output[n-1-i]*=suf_pro; 11 suf_pro*=nums[n-1-i]; 12 } 13 return output; 14 } 15 };

1 class Solution { 2 public: 3 int missingNumber(vector<int>& nums) { 4 int n=nums.size(),tot=0; 5 for(int i=0;i<n;i++){ 6 tot+=nums[i]; 7 } 8 return n*(n+1)/2-tot; 9 } 10 };

相关推荐