DeepSeek LeetCode 2449.使数组相似的最少操作次数 public long makeSimilar(int[] nums, int[] target)

这是一道有趣的题目。我来分析一下解题思路解题思路核心观察1. 因为每次操作可以对任意两个数同时加1和减1所以· 整个数组的总和保持不变· 每个数的奇偶性保持不变因为±1会改变奇偶性但成对操作保证整体奇偶性不变2. 因此nums[i] 和 target[i] 必须具有相同的奇偶性才能通过操作匹配3. 操作的本质是将一个数减少1另一个数增加1所以需要将过大的数减到目标过小的数增加到目标算法步骤1. 将 nums 和 target 按奇偶分别排序2. 在相同奇偶性组内将 nums 中的数与 target 中的数配对nums[i] 配对 target[i]3. 计算差值每个正差值需要减小的数需要若干次操作每个负差值需要增大的数需要若干次操作4. 由于操作是成对的答案就是所有正差值之和除以 2因为每次操作只能改变差值 2代码实现javapublic long makeSimilar(int[] nums, int[] target) {// 分离奇偶数ListInteger oddNums new ArrayList();ListInteger evenNums new ArrayList();ListInteger oddTarget new ArrayList();ListInteger evenTarget new ArrayList();for (int num : nums) {if (num % 2 0) {evenNums.add(num);} else {oddNums.add(num);}}for (int t : target) {if (t % 2 0) {evenTarget.add(t);} else {oddTarget.add(t);}}// 排序Collections.sort(oddNums);Collections.sort(oddTarget);Collections.sort(evenNums);Collections.sort(evenTarget);long ans 0;// 处理奇数部分for (int i 0; i oddNums.size(); i) {int diff oddNums.get(i) - oddTarget.get(i);if (diff 0) {ans diff;}}// 处理偶数部分for (int i 0; i evenNums.size(); i) {int diff evenNums.get(i) - evenTarget.get(i);if (diff 0) {ans diff;}}// 每次操作可以使正差值减少2减少1和增加1算一次操作return ans / 2;}时间复杂度 O(n log n)空间复杂度 O(n)关键点 为什么除以2因为一次操作对两个数分别±1能使正差值总和减少2所以需要的操作次数就是总正差值的一半。