Medium

题目描述

给定一个正整数 n 和一个整数 target。

返回长度为 n 的整数数组，使得：

  • 数组元素的和等于 target
  • 数组元素绝对值组成大小为 n 的排列

如果不存在这样的数组，返回空数组。

大小为 n 的排列是整数 1, 2, ..., n 的重新排列。

示例 1：

输入：n = 3, target = 0
输出：[-3,1,2]
解释：
和为 0 且绝对值组成大小为 3 的排列的数组有：
[-3, 1, 2]、[-3, 2, 1]、[-2, -1, 3]、[-2, 3, -1]、[-1, -2, 3]、[-1, 3, -2]、[1, -3, 2]、[1, 2, -3]、[2, -3, 1]、[2, 1, -3]、[3, -2, -1]、[3, -1, -2]
其中字典序最小的是 [-3, 1, 2]。

示例 2：

输入：n = 1, target = 10000000000
输出：[]
解释：
不存在和为 10000000000 且绝对值组成大小为 1 的排列的数组。因此答案是 []。

约束条件：

  • 1 <= n <= 10^5
  • -10^10 <= target <= 10^10

解题思路

这道题的核心思路是贪心算法，我们需要构造一个字典序最小的数组，其元素绝对值为 1 到 n 的排列，且和为目标值。

分析过程：

  1. 可行性判断：首先考虑所有数为正数的情况，此时和为 S = n*(n+1)/2。通过将某些正数变为负数来调整总和。如果将数字 x 从正变负，总和减少 2x。

  2. 边界条件：

    • 如果 target > S，无解（即使全为正数也达不到）
    • 如果 target < -S，无解（即使全为负数也达不到）
    • 如果 (S - target) 为奇数，无解（因为每次翻转改变偶数）

  3. 贪心策略：设 D = S - target，我们需要通过翻转一些数字使总和减少 D。为了得到字典序最小的结果，应该从大到小考虑翻转数字。这样可以确保较小的正数尽可能保持正号，出现在数组前面。

  4. 构造结果：确定每个数字的符号后，按升序排列即可得到字典序最小的结果。

算法步骤：

  • 计算所有正数的和 S
  • 检查可行性
  • 从 n 到 1 贪心地选择要翻转的数字
  • 构造最终数组并排序

代码实现

class Solution {
public:
    vector<int> lexSmallestNegatedPerm(int n, long long target) {
        long long S = (long long)n * (n + 1) / 2;
        
        // Check feasibility
        if (target > S || target < -S || (S - target) % 2 == 1) {
            return {};
        }
        
        long long D = S - target;
        vector<bool> isNegative(n + 1, false);
        
        // Greedily choose numbers to flip
        for (int i = n; i >= 1 && D > 0; i--) {
            if (2LL * i <= D) {
                isNegative[i] = true;
                D -= 2LL * i;
            }
        }
        
        // Build result array
        vector<int> result;
        for (int i = 1; i <= n; i++) {
            result.push_back(isNegative[i] ? -i : i);
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
        S = n * (n + 1) // 2
        
        # Check feasibility
        if target > S or target < -S or (S - target) % 2 == 1:
            return []
        
        D = S - target
        is_negative = [False] * (n + 1)
        
        # Greedily choose numbers to flip
        for i in range(n, 0, -1):
            if D > 0 and 2 * i <= D:
                is_negative[i] = True
                D -= 2 * i
        
        # Build result array
        result = []
        for i in range(1, n + 1):
            result.append(-i if is_negative[i] else i)
        
        result.sort()
        return result

public class Solution {
    public int[] LexSmallestNegatedPerm(int n, long target) {
        long S = (long)n * (n + 1) / 2;
        
        // Check feasibility
        if (target > S || target < -S || (S - target) % 2 == 1) {
            return new int[0];
        }
        
        long D = S - target;
        bool[] isNegative = new bool[n + 1];
        
        // Greedily choose numbers to flip
        for (int i = n; i >= 1 && D > 0; i--) {
            if (2L * i <= D) {
                isNegative[i] = true;
                D -= 2L * i;
            }
        }
        
        // Build result array
        int[] result = new int[n];
        for (int i = 1; i <= n; i++) {
            result[i - 1] = isNegative[i] ? -i : i;
        }
        
        Array.Sort(result);
        return result;
    }
}

var lexSmallestNegatedPerm = function(n, target) {
    const sum = n * (n + 1) / 2;
    
    if (Math.abs(target) > sum || (sum - target) % 2 !== 0) {
        return [];
    }
    
    const result = [];
    const used = new Set();
    let remaining = target;
    
    for (let pos = 0; pos < n; pos++) {
        for (let val = -n; val <= n; val++) {
            if (val === 0 || used.has(Math.abs(val))) continue;
            
            const newRemaining = remaining - val;
            const remainingPositions = n - pos - 1;
            
            if (remainingPositions === 0) {
                if (newRemaining === 0) {
                    result.push(val);
                    return result;
                }
                continue;
            }
            
            const availableNums = [];
            for (let i = 1; i <= n; i++) {
                if (!used.has(i) && i !== Math.abs(val)) {
                    availableNums.push(i);
                }
            }
            
            if (availableNums.length !== remainingPositions) continue;
            
            let minSum = 0, maxSum = 0;
            for (let num of availableNums) {
                minSum -= num;
                maxSum += num;
            }
            
            if (newRemaining >= minSum && newRemaining <= maxSum && 
                (maxSum - newRemaining) % 2 === 0) {
                result.push(val);
                used.add(Math.abs(val));
                remaining = newRemaining;
                break;
            }
        }
    }
    
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销在最后的排序步骤
空间复杂度O(n)需要额外的数组存储结果和标记