did i finished in linear time and space? [c++](*^__^*)


  • 0

    i don't know if this is correct, cuz the bit of the largest number is const and also the number of bucket is(total ten buckets)

    int maximumGap(vector<int>& nums) {
      if(nums.size()<2) return 0;
      int res=INT_MIN;
      for(int i=0;i<nums.size();i++) //find the largest number in the array.
          res=max(res,nums[i]);
      int weishu=0;
      while(res){//get the width of the largest number
          weishu++;
          res/=10;
      }
      res=INT_MIN;
      int divd=1;
      for(int m=0;m<weishu;m++){
          unordered_map<int,vector<int> > mp;//0-9 bucket
          for(int i=0;i<nums.size();i++){
              int loc=(nums[i]/divd)%10;
              mp[loc].push_back(nums[i]);
          }
          //reload
          for(int i=0,j=0;i<10;i++){
              for(int k=0;k<mp[i].size();k++)
              {
                  nums[j++]=mp[i][k];
              }
          }
          divd*=10;//十位看完看百位
      }
    //after sorted.
      for(int i=1;i<nums.size();i++){
          res=max(nums[i]-nums[i-1],res);
      }
      return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.