Java Sorting with Lambda Expression

问题: I am new to Java and this might be a dumb question to ask. I was looking at '905. Sort Array By Parity' on Leetcode. One of the solutions is class Solution { public i...

问题:

I am new to Java and this might be a dumb question to ask. I was looking at '905. Sort Array By Parity' on Leetcode. One of the solutions is

class Solution {
    public int[] sortArrayByParity(int[] A) {
        Integer[] B = new Integer[A.length];
        for (int t = 0; t < A.length; ++t)
            B[t] = A[t];

        Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

        for (int t = 0; t < A.length; ++t)
            A[t] = B[t];
        return A;

        /* Alternative:
        return Arrays.stream(A)
                     .boxed()
                     .sorted((a, b) -> Integer.compare(a%2, b%2))
                     .mapToInt(i -> i)
                     .toArray();
        */
    }
}

I am having trouble understanding the line with lambda expression in it.

Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

How does it sort the array exactly? Where do a and b come from?


回答1:

Sort

The Java Arrays.sort(B) method takes an array B as input and sorts it according to the compare(a, b) method of B's elements. So if the array stored Integer objects, it would sort them according to Integer.compare(a, b) by default. This just sorts the integers in increasing order.

Comparator

Java has a Comparator interface (see link below) that defines a method called compare(a, b). This method returns zero if (a==b), a negative value if (a < b), and a positive value if (a > b). The Comparator interface is often used in sorting methods or ordered data structures, like TreeMap.

Lambda

Now since this question asks for a custom sort order, you need to provide a custom compare(a, b) method. Fortunately, the Arrays.sort method allows you to do exactly this by providing a lambda method. A lambda is simply an inline function. In this case, it provides the desired comparison logic for the sort. In your example, (a, b) -> are the inputs to the lambda function, which are provided by the sort method. This is standard lambda syntax. The sort will run a mergesort algorithm on the array B, using your lambda compare method to determine how each pair of numbers are ordered.

The Tricky Part

Integer.compare(a%2, b%2) sorts integers a and b according to their least significant bits. % is the modulus operator (remainder after division). If a is even, a%2 returns 0. If a is odd, a%2 returns 1. https://leetcode.com/articles/sort-array-by-parity/ does a decent job of breaking down the logic of why this operation sorts the numbers by parity, but it's not really obvious. The more problems you solve, the more shortcuts like this you will learn.

References

Here are some SO threads that provide more information:

Here's the official Java documentation, but you might want to also look for some easy-to-understand tutorials. Good luck!


回答2:

You are calling Arrays.sort(T[] a, Comparator<? super T> c), where T is resolved by the compiler to Integer, which means that the lambda expression must implement method compare(Integer o1, Integer o2).

a and b are the two parameters to the method. That's how lambda expressions work, you must name (and optionally type) the formal parameters of the abstract method of the functional interface.


回答3:

  • For interviews, as much as you can, you should avoid using Java's specialized methods.

  • You can use this Solution, which is much simple to understand and is interview friendly.

Accepted Solution:

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if (A[left] % 2 == 0)
                left++;

            else {
                if (A[right] % 2 != 0)
                    right--;

                if (A[right] % 2 == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if ((A[left] & 1) == 0)
                left++;

            else {
                if ((A[right] & 1) != 0)
                    right--;

                if ((A[right] & 1) == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

References & Good to Knows

  • For additional details, you can see the Discussion Board. In the Discussion Board, there are plenty of accepted solutions, explanations, efficient algorithms with a variety of languages, and time/space complexity analysis.

If you are leetcoding for interviews:

  • Try to write clean and bug-free codes with proper variable names and consistent coding style.

If you are leetcoding for contests:

  • Just code as fast as you can, almost everything else is very unimportant.
  • For easy questions, brute force algorithms usually get accepted by LeetCode's online judge.
  • For medium and hard questions, brute force algorithms fail with Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors about 90% of the time.
  • For each incorrect submission, there is a time penalty, which will be added to your total time.
  • 发表于 2020-06-27 19:26
  • 阅读 ( 135 )
  • 分类:sof

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除