[Swift]LeetCode667.优美的排列II|BeautifulArrangementII

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

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

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

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

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

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

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

The n and k are in the range 1 <= k < n <= 10^4.

给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：

① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2- a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.

② 如果存在多种答案，你只需实现并返回其中任意一种.

示例 1:

输入: n = 3, k = 1
输出: [1, 2, 3]
解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1

示例 2:

输入: n = 3, k = 2
输出: [1, 3, 2]
解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2

提示:

n 和 k 满足条件 1 <= k < n <= 10^4.

Runtime: 28 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func constructArray(_ n: Int, _ k: Int) -> [Int] {
 3         var k = k
 4         var res:[Int] = [Int]()
 5         var i:Int = 1
 6         var j:Int = n
 7         while (i <= j)
 8         {
 9             var num:Int = 0
10             if k > 1
11             {
12                 if k % 2 != 0
13                 {
14                     num = i
15                     i += 1 
16                 }
17                 else
18                 {
19                     num = j
20                     j -= 1
21                 }
22                 k -= 1                               
23             }
24             else
25             {
26                 num = i
27                 i += 1 
28             }
29             res.append(num)
30         }        
31         return res
32     }
33 }

36ms

 1 class Solution {
 2     func constructArray(_ n: Int, _ k: Int) -> [Int] {
 3         var res = Array(repeating: 0, count: n)
 4         var l = 1, r = n
 5         for i in 0..<k {
 6             if i % 2 == 0 {
 7                 res[i] = l
 8                 l += 1
 9             } else {
10                 res[i] = r
11                 r -= 1
12             }
13         }
14         if k % 2 == 1 {
15             for i in k..<n {
16                 res[i] = l
17                 l += 1
18             }            
19         } else {
20             for i in k..<n {
21                 res[i] = r
22                 r -= 1
23             }              
24         }
25 
26         return res
27     }
28 }

44ms

 1 class Solution {
 2     func constructArray(_ n: Int, _ k: Int) -> [Int] {
 3         if k == 1 { return Array(1 ... n) }
 4         
 5         func gen(_ k: Int) -> [Int] {
 6             var ret = Array(repeating: 0, count: k)
 7             for i in ret.indices {
 8                 ret[i] = i % 2 == 0 ? i/2 + 1 : k - i/2
 9             }
10             return ret
11         }
12         
13         if k + 1 == n { return gen(n) }
14         return gen(k + 1) + Array(k + 2 ... n)
15     }
16 }

60ms

 1 class Solution {
 2     func constructArray(_ n: Int, _ k: Int) -> [Int] {
 3         var result = [Int](repeating: 0, count: n)
 4         
 5         var j = 0
 6         for i in 0..<(n - k - 1) {
 7             result[i] = i + 1
 8             j += 1
 9         }
10         
11         for i in 0...k {
12             result[j] = i % 2 == 0 
13                 ? n - k + i / 2
14                 : n - i / 2
15             j += 1
16         }
17         
18         return result
19     }
20 }