Epoch

題目

  Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is increasing a selected element by 1 or decrementing a selected element by 1.

You may assume the array's length is at most 10,000.

題意

  給一些數字，你要找出某個數字，然後讓所有數字都變成那個數字，過程中所需的增加或減少為一個單位，找到需要最少的單位。

想法

  是個找中位數的問題，當你找到中位數後，把每個數字做加加減減後，計算加減的次數極為所求。

步驟

  1. 排序

  2. 找中位數

  3. 計算次數

程式碼

  int minMoves2(int* nums, int numsSize) {
    int i, j, tmp;
    for(i=0; i<numsSize; i++){
        for(j=i+1; j<numsSize; j++){
            if(nums[i]>nums[j]){
                tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }
        }
    }
    int mid;
    int sum=0;
    mid=numsSize/2;
    for(i=0; i<numsSize; i++){
        sum+=abs(nums[i]-nums[mid]);
    }
    return sum;
}