My sort method meets error


  • 0
    K

    Dear all, I use quick sort to do pre-process, however, it meets error as "runtime error". I use sort method in <algorithm>, then it is accepted.
    I have two question:

    1. Does it a linear method? I don't think so.
    2. what's wrong in my quick sort?
      code is below:
         #include <algorithm>
    // my quick sort
        int Compare(const void *elem1, const void *elem2)
        {
            return *((int *)(elem1)) - *((int *)(elem2)) > 0 ? 1 : -1;
        }
        
        class Solution {
        public:
        
            int singleNumber(int A[], int n)
            {
        
                if (n == 1 || n&0x01 == 0)
                {
                    return A[0];
                }
        
                //qsort(A, n, sizeof(int), Compare); // my qsort
                sort(A, A+n); // accept method
        
                for (int i=1; i<n; i+=2)
                {
                    if (A[i]^A[i-1])
                        return A[i-1];
                }
                return A[n-1];
            }
        };

  • 0
    S

    I believe using quick sort could never be a liner solution, since it is O(N log N).


  • 0
    K

    yes, of cause. do you have liner solution ?


  • 0
    I

    I met the same question. After changing qsort to sort, the problem was solved. I was confused about the qsort, it must be quicker than sort as some experiments show, then why qsort can't pass ?


  • 0
    I

    But qsort is indeed quicker than sort. why RE?


  • 0
    K

    Sure, I think qsort is quicker than sort. Maybe it's a overflow question. However, it's my guess. I will check qsort and sort to find their difference. ;)


  • 0
    S

    @ideno, as far as I know, qsort and sort are same.


  • 0
    S

    @kaleguan, look around in single number category, you might find some posts helpful. For example, this one


  • 0
    D

    change

       return *((int *)(elem1)) - *((int *)(elem2)) > 0 ? 1 : -1;
    

    to

     return (*((int *)(elem1)) > *((int *)(elem2))) ? 1 : -1;
    

    will make qsort work.

    I think the reason is that the former one could cause integer overflow


Log in to reply
 

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