[Swift]LeetCode462.最少移动次数使数组元素相等II|MinimumMovestoEqualArrayElements ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9792341.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

Example:

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

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

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

例如:

输入:
[1,2,3]

输出:
2

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

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

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {
 3         //转换为变量
 4         var arr:[Int] = nums
 5         //对数组进行升序排序
 6         //sorted只返回排序数组, sort才会修改原数组
 7         //arr.sort(by: {$1 < $2})
 8         arr = arr.sorted(by: <)
 9         let len = nums.count
10         var res:Int = 0, mid:Int = arr[len / 2]
11         for num in arr
12         {
13             res += abs(num - mid)
14         }
15         return res
16     }
17 }

24ms

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {
 3         let a = nums.sorted(by:{ $0 < $1 })
 4         var ret = 0 ,i = 0 ,j = nums.count - 1
 5         while i < j {
 6             ret += a[j] - a[i]
 7             j -= 1 ; i += 1
 8         }
 9         return ret
10     }
11 }

28ms

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {        
 3         var i = 0
 4         var j = nums.count - 1
 5         var result = 0
 6         
 7         let sortedNums = nums.sorted(by:{ $0 < $1 })
 8         
 9         while i < j {
10             result += sortedNums[j] - sortedNums[i]
11             i += 1
12             j -= 1
13         }
14         
15         return result
16     }
17 }

32ms

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {
 3         
 4         var _num = nums.sorted(by:<)
 5         
 6         var middleCount = _num.count/2
 7         
 8         var value = _num[middleCount]
 9         var steps = 0
10         for n in _num
11         {
12             if n != value
13             {
14                steps += abs(value - n)
15             }
16             
17         }
18         
19         return steps
20     }
21 }

40ms

 1 class Solution 
 2 {
 3     func minMoves2(_ nums: [Int]) -> Int 
 4     {
 5       
 6         // option 2
 7         let arr = nums.sorted()
 8         var i = 0, j = arr.count - 1
 9         var count = 0
10         while i < j
11         {
12             count += (arr[j] - arr[i])
13             i += 1
14             j -= 1
15         }
16         return count
17     }
18 }

44ms

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {
 3         if (nums.count <= 1) {
 4             return 0
 5         }
 6         
 7         var nums = nums
 8         nums.sort()
 9         
10         var count = 0
11         for i in 0..<nums.count {
12             count += abs(nums[nums.count/2] - nums[i])
13         }
14         return count
15         
16     }
17 }

48ms

 1 class Solution {
 2     func minMoves2(_ nums: [Int]) -> Int {
 3         var raw = nums
 4         raw.sort { (num1, num2) -> Bool in
 5             return num1 < num2
 6         }
 7         var sum: Int = 0
 8         let mean = raw[raw.count / 2]
 9         for i in 0 ..< nums.count {
10             if i < raw.count / 2 {
11                 sum += (mean - raw[i])
12             }else {
13                 sum += (raw[i] - mean)
14             }
15         }
16         return sum
17     }
18 }