C语言 | Leetcode C语言题解之第462题最小操作次数使数组元素相等II

题目：

题解：

static inline void swap(int *a, int *b) {
    int c = *a;
    *a = *b;
    *b = c;
}

static inline int partition(int *nums, int left, int right) {
    int x = nums[right], i = left - 1;
    for (int j = left; j < right; ++j) {
        if (nums[j] <= x) {
            swap(&nums[++i], &nums[j]);
        }
    }
    swap(&nums[i + 1], &nums[right]);
    return i + 1;
}

static inline int randomPartition(int *nums, int left, int right) {
    int i = rand() % (right - left + 1) + left;
    swap(&nums[i], &nums[right]);
    return partition(nums, left, right);
}

static int quickSelect(int *nums, int left, int right, int index) {
    int q = randomPartition(nums, left, right);
    if (q == index) {
        return nums[q];
    } else {
        return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
    }
}

int minMoves2(int* nums, int numsSize){
    srand(time(0));
    int n = numsSize, x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;
    for (int i = 0; i < n; ++i) {
        ret += abs(nums[i] - x);
    }
    return ret;
}

原文地址：https://blog.csdn.net/m0_59237910/article/details/142749898

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！