算法：数组去重并排序-20241103

一、题目 §

题目：
给定一个乱序的数组，删除所有的重复元素，使得每个元素只出现一次，并且按照出现的次数从高到低进行排序，相同出现次数按照第一次出现顺序进行先后排序。
备注: 数组大小不超过100 数组元素值大小不超过100。

输入：
一个数组

输出：
去重排序后的数组

示例：
输入：
1,3,3,3,2,4,4,4,5
输出：
3,4,1,2,5

二、题解 §

基本思路是通过 Map 来记录每个元素出现的次数和记录每个元素第一次出现的位置，先按 map 的 value 降序排序，再按出现位置升序排序。

Python 代码比起 Java 要简洁一些。特地对比了一下。

package org.stone.study.algo.ex202411;
 
import java.util.*;
 
public class DedupAndSort {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 1,3,3,3,2,4,4,4,5
        String[] arr = scanner.nextLine().split(",");
        // 从字符串数组转化为整数数组
        int[] nums = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        int[] res = dedupAndSort(nums);
        System.out.println(Arrays.toString(res));
    }
 
    public static int[] dedupAndSort(int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return new int[0];
        }
 
        // 统计每个数字出现的次数和第一次出现的位置
        HashMap<Integer, Integer> cntMap = new HashMap<>();
        HashMap<Integer, Integer> firstOccurMap = new HashMap<>();
        for(int i = 0; i < n; i++) {
            cntMap.put(nums[i], cntMap.getOrDefault(nums[i], 0) + 1);
            firstOccurMap.putIfAbsent(nums[i], i);
        }
 
        // 对 map 按 value 降序排序，再按 key 在数组中的位置升序排序
        List<Integer> keyList = new ArrayList<>(cntMap.keySet());
        keyList.sort((a, b) -> {
            int freqDiff = cntMap.get(b) - cntMap.get(a);
            if(freqDiff == 0) {
                return firstOccurMap.get(a) - firstOccurMap.get(b);
            } else {
                return freqDiff;
            }
        });
        // 从 List 转化为数组
        return keyList.stream().mapToInt(Integer::intValue).toArray();
    }
}
 
 

from collections import defaultdict
 
def sort_by_frequency(nums):
    first_occurance = {}
    freq = defaultdict(int)
    for index, num in enumerate(nums):
        freq[num] += 1
        if num not in first_occurance:
            first_occurance[num] = index
 
    # freq + first_occurance 转化为 list
    freq_list = [(num, freq[num], first_occurance[num]) for num in freq]
    # 按照 freq 降序，first_occurance 升序排序
    freq_list.sort(key=lambda x: (-x[1], x[2]))
 
    # 只返回 num
    return [x[0] for x in freq_list]
 
if __name__ == "__main__":
    # 1,3,3,3,2,4,4,4,5
    nums = list(map(int, input().split(",")))
    # 3,4,1,2,5
    print(sort_by_frequency(nums))