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

  • 9

    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 {
        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) 
                  //the difference between i and j is at most k
                  if(abs(numptrs[j] - numptrs[i]) <= k) return true;
           return false;

  • 1

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

  • 1

    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.