LeetCode 667. Beautiful Arrangement II
Question
Given two integers n
and k
, you need to construct a list which contains n
different positive integers ranging from 1
to 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.
Note:
- The
n
andk
are in the range 1 <= k < n <= 104.
Example
1 | Input: n = 3, k = 1 |
Solution
本题主要是构造目标数组,其元素之间的差值的不同个数为k。输入确定为[1, 2, ... n]
,想构造该数组,即需要Greedy的思想,构造尽可能多的不同差值的情况。我们可以使用Two Pointer
,当K大于1的时候,需要分别从左右获取元素(构成不同大小的差值情况);当K等于1的时候,即不需要更多的差值,所以只需要升序取完剩下元素即可。
Code
1 | package com.leetcode.greedy; |