C code, 15ms, using QuickSort


  • 2
    F
    int QuickSort(int a[], int left, int right)
    {
        if (left < right)
        {
            int i = left, j = right, p = a[i];
            while (i < j)
            {
                while (i < j && p < a[j])
                    j--;
                if (i < j)
                    a[i++] = a[j];
            
                while (i < j && p > a[i])
                    i++;
                if (i < j)
                    a[j--] = a[i];
            }
            a[i] = p;
        
            QuickSort(a, left, i - 1);
            QuickSort(a, i + 1, right);
        }
    }
    
    int majorityElement(int num[], int n) {
        QuickSort(num, 0, n - 1);
        
        if (n == 1)
            return num[0];
        
        int count = 0, max = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (num[i] == num[i + 1])
                count++;
            if (count > max)
                max = count;
            if (max + 1 > n / 2)
                return num[i];
        }
    }

  • 1
    R

    Haha, I also thought about this way.
    In C#:
    List<int> list = new List<int>(num);
    list.sort();
    return list[num.Length / 2];


  • 0
    F

    That's a really fast way, but my goal is to implement the algorithm by myself.


Log in to reply
 

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