标签： easy

目标

给你一个整数数组 nums ，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

说明：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

思路

长度为 2 * n 数组 nums 有 n + 1 个不同元素，其中恰好有一个元素重复 n 次，返回该重复元素。

除了该重复元素，其余元素各不相同。

暴力做法是使用哈希表记录元素的出现次数，如果出现次数大于 1，直接返回，空间复杂度为 O(n)。

对于本题，从下标 1 开始与第一个元素比较，如果相等直接返回。否则问题变成从 2n - 1 个元素中找重复 n 次的元素，重复元素占绝对多数，可以使用摩尔投票算法。

还可以根据重复元素的最小间隔来分析：

• 假设重复元素至少隔着一个其它元素，有 n - 1 个空隙，至少有 2 * n - 1 个元素，可能。
• 假设重复元素至少隔着两个其它元素，有 n - 1 个空隙，至少有 n + 2 * (n - 1) = 3 * n - 2 个元素，当 n = 2 时，有可能，当 n > 2 时，必定存在一个重复元素的间隔小于 2，否则元素个数不够。

也就是说，可以检查当前元素与其前 1、2、3 个元素是否相等来找出该重复元素。空间复杂度为 O(1)。

以上算法的时间复杂度均为 O(n)，还有一种期望 O(1) 的算法，使用随机数，随机选取两个元素。它们两个相等的概率是 n/2n × (n - 1)/(2n - 1) = 1/2 * (1 - 1/n)/(2 - 1/n)，当 n = 2 时，p = 1/6，当 n -> ∞，p -> 1/4。期望循环次数 <= 6。

代码

/**
 * @date 2026-01-04 14:45
 */
public class RepeatedNTimes961 {

    public int repeatedNTimes_v1(int[] nums) {
        int n = nums.length;
        int candidate = 0;
        int vote = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (vote == 0) {
                candidate = nums[i];
                vote = 1;
            } else if (candidate != nums[i]) {
                vote--;
            } else {
                return candidate;
            }
        }
        return candidate;
    }

    public int repeatedNTimes(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] || (i >= 2 && nums[i] == nums[i - 2]) || (i >= 3 && nums[i] == nums[i - 3])) {
                return nums[i];
            }
        }
        return 0;
    }

}

性能

目标

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

说明：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits 不包含任何前导 0。

思路

数组 digits 表示一个数字，高位在前低位在后，不含前导零，将该数字加一后返回。

由于存在进位，数组长度可能增加 1 位。仔细想想，第一位是 1 后面全是 0。

从后向前遍历，如数字不是 9，将数字加一直接返回，否则，将当前位置零，继续向前进位。如果遍历结束还没有返回，说明数组长度不够，新建数组，将第一位置 1 即可。

代码

/**
 * @date 2024-06-27 0:40
 */
public class PlusOne66 {

    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + 1;
            if (sum == 10) {
                digits[i] = 0;
            } else {
                digits[i] = sum;
                return digits;
            }
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
    }

}

性能

目标

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

思路

有一个 m x n 矩阵 grid，按行按列非严格递减，统计其中的负数个数，要求时间复杂度为 O(m + n)。

暴力做法的复杂度为 O(m x n)。根据矩阵有序的性质，如果 grid[i][j] < 0，那么 grid[i + k][j] < 0，对于 i + k 行，只需继续向前判断，累加当前行的负数个数即可。

代码

/**
 * @date 2025-12-30 11:26
 */
public class CountNegatives1351 {

    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int i = 0, j = n - 1;
        int res = 0;
        while (i < m) {
            while (j >= 0 && grid[i][j] < 0) {
                j--;
            }
            res += n - j - 1;
            i++;
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

说明：

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• 输入数据保证可以将包裹中的苹果重新分装到箱子中。

思路

apple[i] 表示第 i 个包裹中苹果的数量，capacity[i] 表示第 i 个箱子的容量，现在需要将包裹中的苹果分装到箱子中，求所需箱子的最小数量。

累加所有苹果的数量，优先选择容量大的箱子装箱，记录箱子个数。

代码

/**
 * @date 2025-12-24 8:44
 */
public class MinimumBoxes3074 {

    public int minimumBoxes(int[] apple, int[] capacity) {
        int sum = 0;
        for (int num : apple) {
            sum += num;
        }
        Arrays.sort(capacity);
        int res = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {
            if (sum <= 0) {
                break;
            }
            sum -= capacity[i];
            res++;
        }
        return res;
    }
}

性能

目标

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按字典序非严格递增排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格示意如下：
  zyx
  wvu
  tsr
所有 3 列都是非升序排列的，所以都要删除。

说明：

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] 由小写英文字母组成

思路

有一个元素长度相同的字符串数组 strs，删掉其中不是非严格递增的列，返回删除的列数。

枚举每一列，判断是否非严格递增。

代码

/**
 * @date 2025-12-21 20:11
 */
public class MinDeletionSize944 {

    public int minDeletionSize(String[] strs) {
        int m = strs[0].length();
        int res = 0;
        for (int i = 0; i < m; i++) {
            char prev = 0;
            for (String str : strs) {
                char cur = str.charAt(i);
                if (cur < prev) {
                    res++;
                    break;
                }
                prev = cur;
            }
        }
        return res;
    }
}

性能

目标

一个 平方和三元组 (a,b,c) 指的是满足 a² + b² = c² 的 整数 三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

说明：

• 1 <= n <= 250

思路

统计满足 a² + b² = c²，且 1 <= a,b,c <= n 的三元组个数。

暴力枚举 a b，判断平方和是否小于 n²，同时判断开根号之后是否是整数。

代码

/**
 * @date 2025-12-08 8:55
 */
public class CountTriples1925 {

    public int countTriples(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i && i * i + j * j <= n * n; j++) {
                int s = i * i + j * j;
                int k = (int) Math.sqrt(s);
                if (s == k * k){
                    res++;
                }
            }
        }
        return res * 2;
    }

}

性能

目标

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

说明：

• 0 <= low <= high <= 10^9

思路

返回 low 到 high 之间的奇数数目。

如果数字个数是偶数，返回 (high - low + 1) / 2，否则，取决于 high 是奇数还是偶数，如果是奇数，需要再额外加上 1。

代码

/**
 * @date 2025-12-07 22:22
 */
public class CountOdds1523 {

    public int countOdds(int low, int high) {
        int n = high - low + 1;
        return n / 2 + (n % 2 == 0 ? 0 : high % 2);
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 。

分区 是指将数组按照下标 i （0 <= i < n - 1）划分成两个 非空 子数组，其中：

• 左子数组包含区间 [0, i] 内的所有下标。
• 右子数组包含区间 [i + 1, n - 1] 内的所有下标。

对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数 的 分区 方案数。

示例 1：

输入：nums = [10,10,3,7,6]
输出：4
解释：
共有 4 个满足题意的分区方案：
[10]、[10, 3, 7, 6] 元素和的差值为 10 - 26 = -16 ，是偶数。
[10, 10]、[3, 7, 6] 元素和的差值为 20 - 16 = 4，是偶数。
[10, 10, 3]、[7, 6] 元素和的差值为 23 - 13 = 10，是偶数。
[10, 10, 3, 7]、[6] 元素和的差值为 30 - 6 = 24，是偶数。

示例 2：

输入：nums = [1,2,2]
输出：0
解释：
不存在元素和的差值为偶数的分区方案。

示例 3：

输入：nums = [2,4,6,8]
输出：3
解释：
所有分区方案都满足元素和的差值为偶数。

说明：

• 2 <= n == nums.length <= 100
• 1 <= nums[i] <= 100

思路

将数组 nums 划分为非空的左右两部分，满足左子数组的元素和与右子数组的元素和之差为偶数，返回划分的方案数。

数组所有元素和为 sum，假设左子数组和为 left，那么右子树和为 sum - left，二者之差为 2 * left - sum，只需判断 sum 是否是偶数即可，如果是偶数，有 n - 1 种方案，否则没有满足要求的方案。

代码

/**
 * @date 2025-12-05 9:10
 */
public class CountPartitions3432 {

    public int countPartitions(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % 2 == 0 ? nums.length - 1 : 0;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次：

• 选择一个下标 i，并将 nums[i] 替换为 nums[i] - 1。

返回使数组元素之和能被 k 整除所需的最小操作次数。

示例 1：

输入： nums = [3,9,7], k = 5
输出： 4
解释：
对 nums[1] = 9 执行 4 次操作。现在 nums = [3, 5, 7]。
数组之和为 15，可以被 5 整除。

示例 2：

输入： nums = [4,1,3], k = 4
输出： 0
解释：
数组之和为 8，已经可以被 4 整除。因此不需要操作。

示例 3：

输入： nums = [3,2], k = 6
输出： 5
解释：
对 nums[0] = 3 执行 3 次操作，对 nums[1] = 2 执行 2 次操作。现在 nums = [0, 0]。
数组之和为 0，可以被 6 整除。

说明：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 1 <= k <= 100

思路

返回数组元素和模 k 的余数。

代码

/**
 * @date 2025-11-29 21:53
 */
public class MinOperations3512 {

    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % k;
    }
}

性能