【LeetCode】462. 最少移动次数使数组元素相等 II

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:

输入:

[1,2,3]

输出:

2

说明：

只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

思路

寻找中位数

代码

int minMoves2(int* nums, int numsSize) {

    //排序

    for(int i = 0; i < numsSize - 1; i++)

        for( int j = 0; j < numsSize - i - 1; j++)

        {

            if(nums[j] > nums[j+1])

            {

                int tmp = nums[j];

                nums[j] = nums[j+1];

                nums[j+1] = tmp;

            }

        }

    //打印查看

    //for(int i = 0; i < numsSize; i++)

        //printf("%d ", nums[i]);

    //printf("%d\n", (int)floor(numsSize/2) + 1);

    //求中位数

    int mid_num;

    mid_num = nums[numsSize / 2];

    //计算移动数

    double count = 0;

    for(int i = 0; i < numsSize; i++)

        count += abs(mid_num - nums[i]);

    return count;

}

哭笑，难道是用了冒泡排序O(n^2),要熟练一下快排O(nlogn)。