16 ms accepted a unusual C++ solution, even faster than C


  • 9
    T

    I save the nums to a pointer array, then sort the pointer array ascending. At last, I use the most plain algorithm.

    bool cmpptr(int *a, int *b){
        return *a < *b; 
    }
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
          const int N = nums.size();
          vector<int*> numptrs(N);
          for(int i = 0; i < N; ++i){
             numptrs[i] = &nums[i];
          }
          sort(numptrs.begin(), numptrs.end(), cmpptr);
          if(0 == k) return false;
          for(int i = 0; i < N; ++i){
              for(int j = i + 1; j < N; ++j){
                   //nums[i] and nums[j] is at most t
                  if((*numptrs[j]) > (*numptrs[i]) + t) 
                         break;
                  //the difference between i and j is at most k
                  if(abs(numptrs[j] - numptrs[i]) <= k) return true;
              }
          }
           return false;
        }
    
    };

  • 1
    P

    It seems to be O(n^2), but okay~


  • 1
    K

    you should consider complexity for judging a algo or program not a particular set of test cases.


Log in to reply
 

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