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]，要维护两个候选数字（最多有两个元素符合要求），每次有新的数字出现的时候，两个计数器都要减。扫一遍得到两个候选数字后，再扫一遍确认数目是否符合要求。

 class Solution {

 public:

     vector<int> majorityElement(vector<int>& nums) {

         int n=nums.size();

         int num1=-,num2=-,cnt1=,cnt2=;

         for(int i=;i<n;i++){

             if(num1==nums[i]){

                 cnt1++;

             }else if(num2==nums[i]){

                 cnt2++;

             }else if(!cnt1){

                 cnt1++;num1=nums[i];

             }else if(!cnt2){

                 cnt2++;num2=nums[i];

             }else{

                 cnt1--;cnt2--;

             }

         }

         cnt1=cnt2=;

         for(int i=;i<n;i++){

             if(nums[i]==num1)cnt1++;

             if(nums[i]==num2)cnt2++;

         }

         vector<int> aim;

         if(cnt1>n/)aim.push_back(num1);

         if(cnt2>n/)aim.push_back(num2);

         return aim;

     }

 };

229

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

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

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

 class Solution {

 public:

     vector<int> productExceptSelf(vector<int>& nums) {

         int n=nums.size();

         vector<int> pre_pro(n,),suf_pro(n,),output(n);

         for(int i=n-;i>-;i--){

             suf_pro[i]=suf_pro[i+]*nums[i+];

         }

         output[]=suf_pro[];

         for(int i=;i<n;i++){

             pre_pro[i]=pre_pro[i-]*nums[i-];

             output[i]=suf_pro[i]*pre_pro[i];

         }

         return output;

     }

 };

prefix*suffix

击败了7%的用户，恩，意料之中
看一下别人写的
思维被局限了，如果只要求前缀和，我们可以O(1)space来解决，现在多了后缀，也可以，只需要顺序扫的同时把逆序的也处理一下。

 class Solution {

 public:

     vector<int> productExceptSelf(vector<int>& nums) {

         int n=nums.size();

         int pre_pro=,suf_pro=;

         vector<int> output(n,);

         for(int i=;i<n;i++){

             output[i]*=pre_pro;

             pre_pro*=nums[i];

             output[n--i]*=suf_pro;

             suf_pro*=nums[n--i];

         }

         return output;

     }

 };

O(1)space

击败了26%。。。哪里有问题呢。。。。我看了其他的代码，貌似思路都一样，可能是评测机抽风吧

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

268讲的是
给你n个不同的数字，a[i]属于[0,n]，问你缺少了哪个数字

思路
水题。。。n*(n+1)/2减去累加和

 class Solution {

 public:

     int missingNumber(vector<int>& nums) {

         int n=nums.size(),tot=;

         for(int i=;i<n;i++){

             tot+=nums[i];

         }

         return n*(n+)/-tot;

     }

 };

268

巴特西

2017-3-10 leetcode 229 238 268

最新文章

热门文章