标签： 计数排序

目标

给你一个 回文 字符串 s。

返回 s 的按字典序排列的 最小 回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。

排列 是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。

如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

说明：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成。
• 保证 s 是回文字符串。

思路

有一个回文字符串 s，将其重新排列成回文字符串，使得字典序最小。

记录字符串中字符的出现次数，然后按字典序从两边向中间填充，如果出现次数为奇数，那么该字符为中间元素。

代码

/**
 * @date 2026-07-28 9:03
 */
public class SmallestPalindrome3517 {

    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        char[] res = new char[n];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        char mid = 0;
        int cur = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                mid = (char) ('a' + i);
            }
            int k = cnt[i] / 2;
            char c = (char) ('a' + i);
            for (int j = 0; j < k; j++) {
                res[cur + j] = c;
                res[n - cur - j - 1] = c;
            }
            cur += k;
        }
        if (n % 2 == 1) {
            res[n / 2] = mid;
        }
        return new String(res);
    }

}

性能

目标

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr 中 第一个 元素必须为 1 。
• 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

• 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
• 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9

思路

有一个正整数数组 arr，可以将任意元素变成比它更小的正整数，也可以按任意顺序重新排列元素。需要将 arr 变成目标数组，使得第一个元素为 1，且相邻元素差的绝对值不超过 1。返回目标数组可能的最大值。

根据题目要求，第一个元素必须是 1，且相邻元素差的绝对值不超过 1，要使元素值变大只能 +1，且该元素只能由大于等于它的元素转化而来。

贪心策略，从小到大排序数组，遍历数组记录最大值，由于元素值都大于 0，都可以操作成 1，当元素值小于最大值时直接跳过，否则，将元素操作成最大值加一。越大的元素越晚操作，可以使最大值更大。

由于最大值不超过 n，可以将大于 n 的元素都视为 n，这样可以使用计数排序优化。

代码

/**
 * @date 2026-06-29 18:11
 */
public class MaximumElementAfterDecrementingAndRearranging1846 {

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int res = 0;
        for (int num : arr) {
            if (num <= res) {
                continue;
            }
            res++;
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

• 二维数组应该 只 包含数组 nums 中的元素。
• 二维数组中的每一行都包含 不同 的整数。
• 二维数组的行数应尽可能 少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

说明：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= nums.length

思路

将数组转化为二维数组，要求每一行元素没有重复，并且行数尽可能地少。

使用哈希表对相同元素计数，将所有 key 放入一行并将所有 key 的计数减一，如果计数减为 0 则删除 key，直到哈希表为空，时间复杂度为 O(n)。

也可以将哈希表改为数组相当于计数排序。

代码

/**
 * @date 2025-03-19 0:21
 */
public class FindMatrix2610 {

    public List<List<Integer>> findMatrix(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!map.isEmpty()) {
            res.add(new ArrayList<>());
            List<Integer> list = res.get(res.size() - 1);
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                list.add(entry.getKey());
                entry.setValue(entry.getValue() - 1);
                if (entry.getValue() == 0) {
                    iterator.remove();
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

示例 1：

输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。

示例 2：

输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。

说明：

• 1 <= arr.length <= 10^5
• arr.length 为偶数
• 1 <= arr[i] <= 10^5

思路

从整数数组中选出一个元素集合，使该集合中元素在原数组中的出现次数超过原数组长度的一半，求集合大小的最小值。

统计每个元素的出现次数，将出现次数从大到小排序，然后开始选元素直到满足题目条件。

代码

/**
 * @date 2024-12-15 0:17
 */
public class MinSetSize1338 {

    public int minSetSize(int[] arr) {
        int n = arr.length;
        int[] cnt = new int[100001];
        for (int i : arr) {
            cnt[i]++;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int i : cnt) {
            if (i > 0) {
                q.offer(i);
            }
        }
        int res = 0;
        int l = 0;
        while (!q.isEmpty()) {
            l += q.poll();
            res++;
            if (l >= n / 2) {
                break;
            }
        }
        return res;
    }
}

性能

目标

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

• ages[y] <= 0.5 * ages[x] + 7
• ages[y] > ages[x]
• ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

说明：

• n == ages.length
• 1 <= n <= 2 * 10^4
• 1 <= ages[i] <= 120

思路

某社交网站上有 n 个用户，ages[i] 表示用户 i 的年龄，当满足条件 ages[x] >= ages[y] && ages[y] > ages[x] / 2 + 7 时，用户 x 会向 y 发送好友申请。求网站上好友申请的总数。

第三个条件 ages[y] > 100 && ages[x] < 100 即 ages[y] > 100 > ages[x] 与第二个条件重复了，可以不考虑。

ages[x] >= ages[y] > ages[x] / 2 + 7 可以推出 ages[x] > 14 才可以发出好友申请，并且好友申请的对象也要满足 ages[y] > ages[x] / 2 + 7 > 14，

将年龄从大到小排序后，使用滑动窗口计算即可。

瓶颈在于排序，可以使用计数排序。

代码

/**
 * @date 2024-11-17 14:46
 */
public class NumFriendRequests825 {

    public int numFriendRequests_v1(int[] ages) {
        int n = ages.length;
        int[] ageCnt = new int[121];
        for (int i = 0; i < n; i++) {
            ageCnt[ages[i]]++;
        }
        int res = 0, windowCnt = 0;
        int l = 15;
        for (int i = 15; i < 121; i++) {
            windowCnt += ageCnt[i];
            if (l * 2 - 14 <= i) {
                windowCnt -= ageCnt[l++];
            }
            if (windowCnt > 0) {
                res += ageCnt[i] * (windowCnt - 1);
            }
        }
        return res;
    }

    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length;
        int r = n - 1, lowerBounds = ages[r] / 2 + 7;
        int res = 0;
        for (int l = n - 1; l >= 0 && ages[l] > 14; l--) {
            while (ages[l] <= lowerBounds) {
                lowerBounds = ages[--r] / 2 + 7;
            }
            res += r - l;
            int e = l;
            while (e < n - 1 && ages[e] == ages[e + 1]) {
                res++;
                e++;
            }
        }
        return res;
    }
}

性能