2025-12-11：划分数组得到最小 XOR。用go语言，给你一个整数数组 nums 和一个正整数 k。把数组分成 k 段不为

福大大架构师每日一题

发布于 2025-12-19 10:01:00

170

2025-12-11：划分数组得到最小 XOR。用go语言，给你一个整数数组 nums 和一个正整数 k。把数组分成 k 段不为空的连续区间（即 k 个连续的子序列）。对每一段计算区间内所有元素的按位异或（XOR）值，得到 k 个异或结果。取这 k 个结果中的最大值，目标是通过选择划分方式，使这个最大异或值尽可能小，输出该最小可能值。

1 <= nums.length <= 250。

1 <= nums[i] <= 1000000000。

1 <= k <= n。

输入： nums = [1,2,3], k = 2。

输出： 1。

解释：

最优划分是 [1] 和 [2, 3]。

第一个子数组的 XOR 是 1。

第二个子数组的 XOR 是 2 XOR 3 = 1。

子数组中最大的 XOR 是 1，是最小可能值。

题目来自力扣3599。

📋 步骤一：初始化与预处理

1. 计算前缀异或和：首先，代码计算并存储数组的前缀异或和 s。这里 s[i] 表示从数组起始位置到第 i-1 个元素的异或值（s[0] = 0, s[1] = nums[0], s[2] = nums[0] ^ nums[1], 以此类推）。这个预处理的关键在于，任意子数组 nums[j..i-1] 的异或值可以通过 s[i] ^ s[j] 快速得到。
2. 初始化距离矩阵：创建一个二维数组 dis，其维度为 (n+1) x (k+1)。dis[i][k] 表示从数组末尾（索引 n）回溯到当前索引 i，并将这部分数组划分为 k 段时，已经产生的所有分段中的最大异或值的最小可能值。初始时，所有值被设为一个很大的数（math.MaxInt32），表示初始状态下所有状态都是不可达或未优化的。
3. 初始化优先队列：代码定义了一个最小堆（优先队列）PriorityQueue，其中每个元素 Item 包含三个关键信息：当前的最大异或值 d、当前考察的数组索引位置 i、以及剩余的待分段数量 k。堆的排序规则是 d 值小的元素优先级高，这确保了算法总是优先扩展当前最大异或值较小的路径。

🔁 步骤二：优先队列核心循环

算法从数组的末尾（索引 n）开始，此时剩余分段数为 k，当前最大异或值 d 为 0。这个初始状态被加入到优先队列中。

随后进入循环，只要队列不为空，就执行以下操作：

1. 弹出最优状态：从优先队列中弹出 d 值最小的 Item。这保证了算法总是沿着当前看来最有希望（即当前最大异或值最小）的路径进行探索。
2. 检查终止条件：
- • 如果弹出的状态中剩余分段数 k 为 0，并且当前索引 i 也恰好为 0，这意味着数组已经被成功地分成了 k 段，并且我们已经从末尾处理到了数组的开头。此时，该状态下的 d 值就是全局最优解，直接返回。
- • 如果 k 为 0 但 i 不为 0，说明分段已用完但数组还有剩余元素，这不是一个有效的划分，因此跳过。
3. 路径松弛与状态扩展：对于当前弹出的状态 (d, i, k)，算法尝试所有可能的前一个分割点 j（j 从 0 到 i-1）。这意味着它考虑将子数组 nums[j..i-1] 作为新的一段。
- • 计算新段的异或值：利用前缀异或和，新段的异或值快速计算为 segmentXor = s[i] ^ s[j]。
- • 计算新的最大异或值：新的候选最大异或值 newD 是当前路径的最大值 d 和新段异或值 segmentXor 中的较大者，即 newD = max(d, segmentXor)。
- • 更新状态：如果计算得到的 newD 小于 dis 矩阵中在位置 (j, k-1) 记录的值，说明找到了一条到达状态 (j, k-1) 的更优路径（即最大异或值更小）。此时，更新 dis[j][k-1] 为 newD，并将这个新状态 (newD, j, k-1) 加入到优先队列中，以待后续扩展。

📊 复杂度分析

• 总的时间复杂度：该算法的时间复杂度主要由优先队列的操作和状态扩展决定。最坏情况下，需要处理 O(n * k) 个状态（即 dis 矩阵的大小），每个状态最多可能扩展出 O(n) 个新状态（通过内层循环遍历分割点 j）。同时，优先队列的每次插入和弹出操作是 O(log(n*k)) 级别。因此，总的时间复杂度为 O(n² * k * log(n*k))。
• 总的额外空间复杂度：空间消耗主要来自三个方面：
1. 1. dis 距离矩阵：O(n * k)。
2. 2. 优先队列：在最坏情况下可能需要存储 O(n * k) 个元素。因此，总的额外空间复杂度为 O(n * k)。

希望这个详细的分解过程能帮助您完全理解这个解决方案的运作机制。

Go完整代码如下：

package main

import (
    "container/heap"
    "fmt"
    "math"
)

// 定义优先队列元素类型
type Item struct {
    d     int// 当前最大异或值
    i     int// 当前索引
    k     int// 剩余分段数
    index int// 在堆中的索引
}

// 定义优先队列
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { returnlen(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // 按d值从小到大排序
    return pq[i].d < pq[j].d
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func max(a, b int)int {
    if b > a {
        return b
    }
    return a
}

func minXor(nums []int, k int)int {
    n := len(nums)

    // 计算前缀异或和
    s := make([]int, n+1)
    for i := 0; i < n; i++ {
        s[i+1] = s[i] ^ nums[i]
    }

    // 初始化距离矩阵
    dis := make([][]int, n+1)
    for i := range dis {
        dis[i] = make([]int, k+1)
        for j := range dis[i] {
            dis[i][j] = math.MaxInt32
        }
    }

    // 初始化优先队列
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    // 初始状态: 从末尾开始，剩余k个分段
    start := &Item{d: 0, i: n, k: k}
    dis[n][k] = 0
    heap.Push(&pq, start)

    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        d, i, k := item.d, item.i, item.k

        // 如果当前距离不是最优的，跳过
        if d > dis[i][k] {
            continue
        }

        // 如果k==0，检查是否到达起点
        if k == 0 {
            if i == 0 {
                return d
            }
            continue
        }

        // 遍历所有可能的分割点
        for j := 0; j < i; j++ {
            newD := max(d, s[i]^s[j])
            if newD < dis[j][k-1] {
                dis[j][k-1] = newD
                heap.Push(&pq, &Item{d: newD, i: j, k: k - 1})
            }
        }
    }

    // 如果没有找到有效分割，返回0
    return0
}

func main() {
    nums := []int{1, 2, 3}
    k := 2
    result := minXor(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq
import math
from typing import List

class Item:
    __slots__ = ('d', 'i', 'k')
    
    def __init__(self, d: int, i: int, k: int):
        self.d = d  # 当前最大异或值
        self.i = i  # 当前索引
        self.k = k  # 剩余分段数
    
    def __lt__(self, other):
        # 按d值从小到大排序
        return self.d < other.d
    
    def __repr__(self):
        return f"Item(d={self.d}, i={self.i}, k={self.k})"

def minXor(nums: List[int], k: int) -> int:
    n = len(nums)
    
    # 计算前缀异或和
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] ^ nums[i]
    
    # 初始化距离矩阵
    dis = [[math.inf] * (k + 1) for _ in range(n + 1)]
    
    # 初始化优先队列
    pq = []
    
    # 初始状态: 从末尾开始，剩余k个分段
    start = Item(d=0, i=n, k=k)
    dis[n][k] = 0
    heapq.heappush(pq, start)
    
    while pq:
        item = heapq.heappop(pq)
        d, i, k_val = item.d, item.i, item.k
        
        # 如果当前距离不是最优的，跳过
        if d > dis[i][k_val]:
            continue
        
        # 如果k==0，检查是否到达起点
        if k_val == 0:
            if i == 0:
                return d
            continue
        
        # 遍历所有可能的分割点
        for j in range(i):
            new_d = max(d, s[i] ^ s[j])
            if new_d < dis[j][k_val - 1]:
                dis[j][k_val - 1] = new_d
                heapq.heappush(pq, Item(d=new_d, i=j, k=k_val - 1))
    
    # 如果没有找到有效分割，返回0
    return0


# 测试代码
if __name__ == "__main__":
    nums = [1, 2, 3]
    k = 2
    result = minXor(nums, k)
    print(f"最小异或值为: {result}")

C++完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

struct Item {
    int d; // 当前最大异或值
    int i; // 当前索引
    int k; // 剩余分段数

    Item(int d, int i, int k) : d(d), i(i), k(k) {}
};

// 用于优先队列的比较函数（最小堆）
struct CompareItem {
    bool operator()(const Item& a, const Item& b) {
        return a.d > b.d; // 按d值从小到大排序
    }
};

int minXor(vector<int>& nums, int k) {
    int n = nums.size();

    // 计算前缀异或和
    vector<int> s(n + 1, 0);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] ^ nums[i];
    }

    // 初始化距离矩阵
    vector<vector<int>> dis(n + 1, vector<int>(k + 1, INT_MAX));

    // 初始化优先队列（最小堆）
    priority_queue<Item, vector<Item>, CompareItem> pq;

    // 初始状态: 从末尾开始，剩余k个分段
    Item start(0, n, k);
    dis[n][k] = 0;
    pq.push(start);

    while (!pq.empty()) {
        Item item = pq.top();
        pq.pop();

        int d = item.d;
        int i = item.i;
        int k_remain = item.k;

        // 如果当前距离不是最优的，跳过
        if (d > dis[i][k_remain]) {
            continue;
        }

        // 如果k_remain==0，检查是否到达起点
        if (k_remain == 0) {
            if (i == 0) {
                return d;
            }
            continue;
        }

        // 遍历所有可能的分割点
        for (int j = 0; j < i; j++) {
            int newD = max(d, s[i] ^ s[j]);
            if (newD < dis[j][k_remain - 1]) {
                dis[j][k_remain - 1] = newD;
                pq.push(Item(newD, j, k_remain - 1));
            }
        }
    }

    // 如果没有找到有效分割，返回0
    return0;
}

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 2;
    int result = minXor(nums, k);
    cout << result << endl;
    return0;
}