算法：数组去重并排序

一、题目

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

二、题解

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

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

1
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();    }}
1
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();    }}
1
from collections import defaultdictdef 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))
1
from collections import defaultdictdef 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))