V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
jadelike
V2EX  ›  程序员

Collections.sort 里相减怎么判断正/逆序?

  •  
  •   jadelike · 2022-09-19 15:43:03 +08:00 · 1694 次点击
    这是一个创建于 782 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天在做 leetcode 的每日一题( 1636. 按照频率将数组升序排序) java 题解有这么一部分

    class Solution {
        public int[] frequencySort(int[] nums) {
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            for (int num : nums) {
                cnt.put(num, cnt.getOrDefault(num, 0) + 1);
            }
            List<Integer> list = new ArrayList<Integer>();
            for (int num : nums) {
                list.add(num);
            }
            Collections.sort(list, (a, b) -> {
                int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
                return cnt1 != cnt2 ? cnt1 - cnt2 : b - a;
            });
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                nums[i] = list.get(i);
            }
            return nums;
        }
    }
    
    作者:LeetCode-Solution
    链接: https://leetcode.cn/problems/sort-array-by-increasing-frequency/solution/an-zhao-pin-lu-jiang-shu-zu-sheng-xu-pai-z2db/
    来源:力扣( LeetCode )
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    我自己用

    Collections.sort(list, (a, b) -> {
                int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
                return cnt1 != cnt2 ? -1 : 1;
            });
    

    代替,结果错了,请问为什么,我只知道 1 ,-1 判断正序还是逆序,不清楚相减怎么判断逆序还是正序

    12 条回复    2022-09-19 20:36:29 +08:00
    Jooooooooo
        1
    Jooooooooo  
       2022-09-19 15:46:51 +08:00
    sort 里如果相等一定要返回 0.
    hidemyself
        2
    hidemyself  
       2022-09-19 16:02:11 +08:00
    Comparator 要满足自反性,传递性,对称性
    1 ) 自反性:x ,y 的比较结果和 y ,x 的比较结果相反。
    2 ) 传递性:x>y,y>z,则 x>z 。
    3 ) 对称性:x=y,则 x,z 比较结果和 y ,z 比较结果相同。
    AoEiuV020CN
        3
    AoEiuV020CN  
       2022-09-19 16:21:31 +08:00
    一直觉得这个很不直观,可以记个典型,
    123456 从小到大排列,
    sort return a - b 代表从小到大排序,
    也就是返回负数的话 a 会排到左边,

    返回-1 还是-2 没差的,更小的两个还得再比一次,
    另外相等必须 return 0,
    wolfie
        4
    wolfie  
       2022-09-19 16:24:28 +08:00
    > cnt1 != cnt2

    问号脸.jpg
    beimengyeyu
        5
    beimengyeyu  
       2022-09-19 16:28:09 +08:00
    cnt1 - cnt2 可能返回两种结果 正的负的都可能返回的
    dcsuibian
        6
    dcsuibian  
       2022-09-19 16:30:04 +08:00
    其实可以这么记:
    a < b 返回负数,因为 a - b < 0
    a > b 返回正数,因为 a - b > 0
    默认按从小到大排,要聪达到小就反过来减

    更好的方案是 Interget.compare(a,b),避免减法时的移除问题,但算法题不是很需要
    dcsuibian
        7
    dcsuibian  
       2022-09-19 16:31:02 +08:00
    聪达到小 --> 从大到小
    移除问题 --> 溢出
    jadelike
        8
    jadelike  
    OP
       2022-09-19 17:09:54 +08:00
    @dcsuibian
    那就以题目为例子,我要 cnt1 != cnt2 的时候返回的是升序,为什么就一定是 cnt1 - cnt2 ,他怎么知道 cnt1 和 cnt2 的大小的?
    dcsuibian
        9
    dcsuibian  
       2022-09-19 18:03:47 +08:00
    @jadelike 1 和-1 并不对应“升序”或“降序”。而且还有个 0 呢。

    代码里的 (a,b)->{ ... } 这段其实是你对排序方式的定义

    返回值<0 (比如-1 ),指明元素 a 在数组中应该在元素 b 的前面
    返回值>0 (比如 1 ),指明元素 b 在数组中应该在元素 a 的前面

    返回值 0 ,则这两个元素一样,a 前 b 后或 b 前 a 后都可
    dcsuibian
        10
    dcsuibian  
       2022-09-19 18:18:11 +08:00
    @jadelike sort()方法其实永远都是升序排序,也就是小的在前,大的在后

    “小”和“大”的概念很模糊,比如对于一个 Student ,怎么定义小?可以按成绩、姓名、学号等等,因此 (a,b) -> { ... }这段也可以说是定义大小关系,如果返回值<0 ,就认为 a 比 b 小,应该排在前面。如果是数字的话 a-b 正好就<0 。

    降序的功能其实是不存在的,但你可以把返回值的正负号颠倒。这样就实现了降序的效果。
    darkengine
        11
    darkengine  
       2022-09-19 20:26:11 +08:00
    这个 sort 的实现就很诡异啊,你用是否相等来返回-1 和 1 ,那么 list = [3,4]和 list = [4,3]得到的排序结果是不一样的。
    qyc027
        12
    qyc027  
       2022-09-19 20:36:29 +08:00
    结果 > 0 就 swap 。b - a > 0 => b > a ,右边大于左边的时候就交换位置,所以最后左边的都大于右边的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1732 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:41 · PVG 00:41 · LAX 08:41 · JFK 11:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.