How to find a job position

Glassdoor

Indeed

Dice

LinkedIn

根本投不完

50 positions / day -> Impossible

BigData Notes

--------->
Docker
We have a Virtual Machine which has the same environment to the server

The image has everything, it has a complete environment all contained into one

Using the resource and configuration of its host system

It provides and lightweight environment to run your application code. Docker has an efficient workflow for moving your application from developers laptop, test environment to production.

--------->

Why declaring Mapper and Reducer classes as static?

"When declaring mapper and reducer classes as inner classes to another class, they have to be declared static such that they are not dependent on the parent class.

Hadoop uses reflection to create an instance of the class for each map or reduce task that runs. The new instance created expects a zero argument constructor (otherwise how would it know what to pass).

By declaring the inner mapper or reduce class without the static keyword, the java compile actually creates a constructor which expects an instance of the parent class to be passed in at construction.

You should be able to see this by running the javap command against the generated classfile

Also, the static keyword is not valid when used in a parent class declaration (which is why you never see it at the top level, but only in the child classes)"


----->

public static class Map extends Mapper<**LongWritable**, Text, Text, IntWritable>

"TextInputFormat’s keys, being simply the offset within the file, are not normally very useful. It is common for each line in a file to be a key-value pair, separated by a delimiter such as a tab character. For example, this is the output produced by TextOutputFormat, Hadoop’s default OutputFormat. To interpret such files correctly, KeyValueTextInputFormat is appropriate.

523. Continuous Subarray Sum

Version #1 HashMap

239. Sliding Window Maximum

三刷 07/2022

Version #1 Sliding Window

一遍bug free

上次相等时候不应该poll last出来的错误这次没犯

Time O(N)

Space O(k) - the deque containing at most k characters

Runtime: 41 ms, faster than 83.35% of Java online submissions for Sliding Window Maximum.

Memory Usage: 140.5 MB, less than 73.80% of Java online submissions for Sliding Window Maximum.

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        Deque<Integer> deque = new ArrayDeque<>();

        // 1, 2, 3  k = 2

        // 

        int[] result = new int[nums.length - k + 1];

        int start = 0;

        for (int end = 0; end < nums.length; end++) {

            while (!deque.isEmpty() && deque.peekLast() < nums[end]) {

                deque.pollLast();

            }

            deque.offerLast(nums[end]);

            if (end - start + 1 == k) {

                result[start] = deque.peekFirst();

                if (deque.peekFirst() == nums[start]) {

                    deque.pollFirst();

                }

                start++;

            }

        }

        return result;

    }

}

二刷 06/2022

写了一个bug就是当当前值和que.peekLast相等的时候要不要pollLast，答案是不要

举个例子

因为在pollFirst的时候是根据数值remove的

所以需要存duplicate的最大值

[-7,-8,7,5,7,1,6,0]
4

Time O(N)

Space O(k)

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        // [1,3,-1,-3,5,3,6,7]

        // We have a queue, whenever we see a number, we can poll out all elements smaller than current number from the tail of the queue, since we've already have a number larger and will never be removed from the window before those smaller elements

        Deque<Integer> deque = new ArrayDeque<>();

        // 0   1  2

        // [1, 2, 3] k = 2

        // (    )

        //    (    )

        int[] max = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {

            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {

                deque.pollLast();

            }

            deque.addLast(nums[i]);

            // remove the element that's out of the window

            if (i - k >= 0 && deque.peekFirst() == nums[i - k]) {

                deque.pollFirst();

            }

            if (i - k + 1 >= 0) {

                max[i - k + 1] = deque.peekFirst();

            }

        }

        return max;

    }

}

一刷

Version #2 Deque
Time O(n)
Space O(k)

64.14 %
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //            start    end      end - start == k - 1
        // index i  0  1  2  3  4  5
        // nums[i]
        if (nums == null || nums.length == 0) return nums;
       
        // When a number x comes after current max number
        // 1. x >= currMax -> currMax can be replaced by x
        // 2. x < currMax -> it is possible that x is usefull after currMax is passed
        // However, every candidate that is smaller than x will be useless
        // --> candidates before x are all larger than x, currMax is larger than all candidates
        Deque<Integer> candidates = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        int start = 0;
        for (int end = 0; end < nums.length; end++) {
            if (end - start == k) {
                if (nums[start] == candidates.peekFirst()) {
                    candidates.pollFirst();
                }
                start++;
            }
            // add nums[end]
            while (!candidates.isEmpty() && candidates.peekLast() < nums[end]) {
                candidates.pollLast();
            }
            candidates.offerLast(nums[end]);
            if (end - start == k - 1) result[start] = candidates.peekFirst();
        }
        return result;
    }
}


Version #1 Simply remove
15.42 % 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return nums;
        int[] result = new int[nums.length - k + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            pq.add(nums[i]);
            //remove last element
         
            if (i >= k - 1) {
                if (i >= k) pq.remove(nums[i - k]);
                result[i - k + 1] = pq.peek();
            }
         
        }
        return result;
    }
}

238. Product of Array Except Self

Version #1 从左往右扫一遍再从右往左扫一遍
O(1) Space
O(N) Time

三刷

100.00 %
 class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int temp = 1;
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = temp;
            temp *= nums[i];
        }
        temp = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            result[i] *= temp;
            temp *= nums[i];
        }
        return result;
    }
}




29.73 %

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        int leftProduct = 1;
        int rightProduct = 1;
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = leftProduct;
            leftProduct *= nums[i];
        }
        for (int j = nums.length - 1; j >= 0; j--) {
            res[j] = res[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return res;
    }
}

二刷


class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        int[] result  = new int[nums.length];
        int leftProduct = 1;
        int rightProduct = 1;
        for (int i = 0; i < nums.length; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }
        for (int j = nums.length - 1; j >= 0; j--) {
            result[j] = rightProduct * result[j];
            rightProduct *= nums[j];
        }
        return result;
    }
}

Spring Security

You don't need to do anything with cookies in this case.

As long as user is logged in (no matter how he logged in - using login form or "remember me"), you can access UserDetails of that user from SecurityContext, Spring Security takes care of it.

So, all you need is to put the requred information into UserDetails in UserDetailsService.loadUserByUsername() (use your own subclass of UserDetails, if necessary), and access it via SecurityContext:

Authentication auth = SecurityContextHolder.getContext().getAuthentication();
if (auth != null) {
    Object principal = auth.getPrincipal();  
    if (principal instanceof UserDetails) {
        UserDetails user = (UserDetails) principal;
        ... // User is logged in, now you can access its details
    }
}

In other words, when Spring Security receives a request without active session but with remember me cookie, it uses user identity from the cookie to load UserDetails and put them into SecurityContext (and into newly created session session). Later you can access these details from SecurityContext.

81. Search in Rotated Sorted Array II

三刷

Runtime: 1 ms, faster than 80.32% of Java online submissions for Search in Rotated Sorted Array II.

Memory Usage: 43.6 MB, less than 64.65% of Java online submissions for Search in Rotated Sorted Array II.

class Solution {

    public boolean search(int[] nums, int target) {

        if (nums == null) {

            return false;

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                return true;

            }

            if (nums[mid] == nums[start]) {

                start++;

            } else if (nums[mid] == nums[end]) {

                end--;

            } else if (nums[mid] > nums[start]) {

                if (nums[start] <= target && target < nums[mid]) {

                    end = mid - 1;

                } else {

                    start = mid + 1;

                }

            } else {

                if (nums[mid] < target && target <= nums[end]) {

                    start = mid + 1;

                } else {

                    end = mid - 1;

                }

            }

        }

        if (nums[start] == target || nums[end] == target) {

            return true;

        }

        return false;

    }

}

二刷
The only difference is that due to the existence of duplicates, we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.
29.43 %
class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) { // [start, mid] is sorted
                if (nums[start] <= target && nums[mid] > target) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else { // [mid, end] is sorted
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return nums[start] == target;
    }
}

一刷

Submission Result: Wrong Answer More Details 

Input:[1,3,1,1,1] 3

Output:false

Expected:true

3 1 2 3 3 3 3 
3 3 3 3 1 2 3

一开始以为duplicates不会有影响，后来发现too young too simple了
上面是两个反例
所以用< 和 > 判断出fully ordered之后， 还存在start == mid || end == mid 的情况
这种情况下只能排除start和end，所以start++ || end--
Time worst case O(n) General case O(logn)
12.55 %

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        int start = 0, end = nums.length - 1;
        // exit when start == end
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return true;
            // first half is fully ordered
            if (nums[start] < nums[mid]) {
                if (nums[start] <= target && nums[mid] > target) end = mid - 1;
                else start = mid + 1;
            // second half is fully ordered
            } else if (nums[end] > nums[mid]) {
                if (nums[mid] < target && nums[end] >= target) start = mid + 1;
                else end = mid - 1;
            } else {
                if (nums[start] == nums[mid]) start++;
                if (nums[end] == nums[mid]) end--;
            }
        }
        return nums[start] == target;
     
    }
}

33. Search in Rotated Sorted Array

四刷 06/2022

Version #1 One Pass Binary Search

先判断哪边有序

Time O(logN)

Space O(1)

Runtime: 1 ms, faster than 70.07% of Java online submissions for Search in Rotated Sorted Array.

Memory Usage: 42.1 MB, less than 75.19% of Java online submissions for Search in Rotated Sorted Array.

class Solution {

    public int search(int[] nums, int target) {

        if (nums == null || nums.length == 0) {

            return -1;

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                return mid;

            }

            if (nums[mid] > nums[start]) {

                // [start, mid] is sorted

                if (nums[start] <= target && nums[mid] > target) {

                    end = mid - 1;

                } else {

                    start = mid + 1;

                }

            } else {

                // [mid, end] is sorted

                if (nums[mid] < target && nums[end] >= target) {

                    start = mid + 1;

                } else {

                    end = mid - 1;

                }

            }

        }

        if (nums[start] == target) {

            return start;

        }

        return nums[end] == target ? end : -1;

    }

}

三刷 

Runtime: 1 ms, faster than 61.17% of Java online submissions for Search in Rotated Sorted Array.

Memory Usage: 42.7 MB, less than 44.35% of Java online submissions for Search in Rotated Sorted Array.

class Solution {

    public int search(int[] nums, int target) {

        if (nums == null) {

            return -1;

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[start] < nums[mid]) {

                if (nums[start] <= target && nums[mid] >= target) {

                    end = mid;

                } else {

                    start = mid + 1;

                }

            } else {

                if (nums[mid] <= target && nums[end] >= target) {

                    start = mid;

                } else {

                    end = mid - 1;

                }

            }

        }

        if (nums[start] == target) {

            return start;

        }

        if (nums[end] == target) {

            return end;

        }

        return -1;

    }

}

二刷
94.70 %
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[start] <= nums[mid]) { // [start, mid] is sorted
                if (nums[mid] > target && nums[start] <= target) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else { // [mid, end] is sorted
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return nums[start] == target ? start : -1;
    }
}

一刷
BST
先判断哪一边是有序，然后看target是否在有序的side
87.02 %
class Solution {
    /* start  --  mid  -- end
     0. target == mid return true
     1. [start, mid] fully sorted
        a. target is in this range -> end = mid - 1
        b. target is not in this range -> start = mid + 1
     2. [mid, end] fully sorted
        a. target is in this range -> start = mid + 1
        b. target is not in this range -> end = mid -1    
    */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0, end = nums.length - 1;
        // exit when start == end
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return mid;
            // first half is fully ordered
            if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && nums[mid] > target) end = mid - 1;
                else start = mid + 1;
            // second half is fully ordered
            } else {
                if (nums[mid] < target && nums[end] >= target) start = mid + 1;
                else end = mid - 1;
            }
        }
        return nums[start] == target ? start : -1;
    }
}

339. Nested List Weight Sum

Version #1 BFS

一刷

一道简单的bfs
不要被api吓到
每一层的weight是它的depth
所以记一下depth就好了

13.69 %
public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        if (nestedList == null) return 0;
        int sum = 0;
        int depth = 0;
        Queue<NestedInteger> que = new LinkedList<>();
        for (NestedInteger ni : nestedList) que.offer(ni);
        NestedInteger curr = null;
        List<NestedInteger> neighbors = null;
        int levelSum = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            depth++;
            while (size-- > 0) {
                curr = que.poll();
                if (curr.isInteger()) {
                    levelSum += curr.getInteger();
                } else {
                    neighbors = curr.getList();
                    for (NestedInteger neighbor : neighbors) {
                        que.offer(neighbor);
                    }
                }
            }
            sum += levelSum * depth;
            levelSum = 0;
        }
        return sum;
    }
}

Version #2 DFS

果然dfs比bfs快好多

按题意无脑做就行了

Runtime: 0 ms, faster than 100.00% of Java online submissions for Nested List Weight Sum.

Memory Usage: 36.4 MB, less than 75.85% of Java online submissions for Nested List Weight Sum.

class Solution {

    public int depthSum(List<NestedInteger> nestedList) {

        int res = 0;

        for (NestedInteger ni : nestedList) {

            res += sum(ni, 1);

        }

        return res;

    }

    

    private int sum(NestedInteger ni, int depth) {

        if (ni.isInteger()) {

          return depth * ni.getInteger();

        }

        int res = 0;

        for (NestedInteger nextNi : ni.getList()) {

            res += sum(nextNi, depth + 1);

        }

        return res;

    }

}

646. Maximum Length of Pair Chain

用的是greedy的思想
sort all intervals by their end points
Increase the count by 1
Greedily looking for the 1st next point whose start point is larger than the current point
Set current end value as the new current point's end

46.73 %
class Solution {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        // sort by the end point
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));
        int currEnd;
        int count = 0;
        int i = 0;
        while (i < pairs.length) {
            count++;
            currEnd = pairs[i][1];
            i++;
            while (i < pairs.length && pairs[i][0] <= currEnd) {
                i++;
            }
        }
        return count;
    }
}

366. Find Leaves of Binary Tree

Version #2 BFS 想到用topological sort的方法，空间复杂度比DFS高很多，就不考虑了

三刷 08/2022

Version #1 DFS

Time O(N) - number of nodes

Space O(N) - height of the tree

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Leaves of Binary Tree.

Memory Usage: 42.8 MB, less than 18.88% of Java online submissions for Find Leaves of Binary Tree.

class Solution {

    public List<List<Integer>> findLeaves(TreeNode root) {

        // add to result by height

        // height of a node is max(left height, right height) + 1

        List<List<Integer>> result = new ArrayList<>();

        dfs(root, result);

        return result;

    }

    

    private int dfs(TreeNode node, List<List<Integer>> result) {

        if (node == null) {

            return 0;

        }

        int h = 0;

        if (node.left != null || node.right != null) {

            h = 1 + Math.max(dfs(node.left, result), dfs(node.right, result));

        }

        if (result.size() == h) {

            result.add(new ArrayList<>());

        }

        result.get(h).add(node.val);

        return h;

    }

}

Version #1 DFS
二刷
34.30 %
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        // 1 node's height is defined as 1 + min(leftHeight, rightHeight)
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
   
    private int dfs(TreeNode node, List<List<Integer>> result) {
        if (node == null) {
            return Integer.MIN_VALUE;
        }
        int height = 0;
        if (node.left == null && node.right == null) {
            height = 0;
        } else {
            height = 1 + Math.max(dfs(node.left, result), dfs(node.right, result));
        }
        if (result.size() <= height) {
            result.add(new ArrayList<>());
        }
        result.get(height).add(node.val);
        // System.out.println(node.val + " " + height);
        return height;
    }
}
一刷
Using the depth of each node to distinguish their index in the result list
The depth is defined by the depth of its deepest child subtree, plus 1.
Since we are adding the nodes to their corresponding lists while we are traversing the tree, each node is visited only once. So the time complexity is O(n)
Space cost is the system stack used by the recursive call. Even recursion call stopped when we reached the leaf of the tree. So the stack scale is the height of the tree O(h).
这个code应该把depth改成height

17.75 % 
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        //TODO
        findLeavesDFSHelper(root, result);
        return result;
    }
    // return the depth of the current node
    private int findLeavesDFSHelper(TreeNode root, List<List<Integer>> result) {
        if (root == null) return -1;
        int leftDepth = findLeavesDFSHelper(root.left, result);
        int rightDepth = findLeavesDFSHelper(root.right, result);
        int depth = Math.max(leftDepth, rightDepth) + 1;
        if (depth == result.size()) result.add(new ArrayList<Integer>());
        result.get(depth).add(root.val);
        return depth;
    }
}

Nested Integer Summary

最近连着做了两道Nested Integer的题发现都不太会
关键是不知道这个Nested Integer 到底是个啥
看了一下这个blog 说的还不错
盗个图

https://zyfu0408.gitbooks.io/interview-preparation/content/nestedinteger%E7%B1%BB.html

341. Flatten Nested List Iterator

"In the constructor, we push all the nestedList into the stack from back to front, so when we pop the stack, it returns the very first element. Second, in the hasNext() function, we peek the first element in stack currently, and if it is an Integer, we will return true and pop the element. If it is a list, we will further flatten it. This is iterative version of flatting the nested list. Again, we need to iterate from the back to front of the list."

这里我用了一个全局的Next变量cache了hasNext里面的top值

上面的explaination里面用peek() 代替了pop()，在next()里面才pop()，比我写的好一些

43.94 % 
public class NestedIterator implements Iterator<Integer> {
    // Tree in-order traversal
    Stack<NestedInteger> stack = new Stack<>();
    Integer next;
    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
       return next;
    }

    @Override
    public boolean hasNext() {
        NestedInteger curr;
        while (!stack.isEmpty()) {
            curr = stack.pop();
            if (curr.isInteger()) {
                next = curr.getInteger();
                //System.out.println(next);
                return true;
            }
            List<NestedInteger> list = curr.getList();
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
        return false;
    }
}

296. Best Meeting Point

[TODO] bucket sort 其实可以优化成O(mn) 譬如直接用y的顺序add y values / bucket sort(extra space) 但是代码没有这样的简洁 有空可写
Version #1 Sorting the points

一刷
另外一个简化

// hi - mid +  mid - lo = hi - lo

感觉不这么写也可以，就是效率稍微低一点

关于为什么median是best meeting point 的证明
For two points, any position between those two points is OK. Since the sum of their path is always the distance between those two.
For 3 points, the sum distance for the two edge points are always the same. However the meeting point's position will influence the middle point's journey. So the best point is the middle point.

For even number of points, any position between the two middle point is fine.
For odd number of points, the median point is the best position.

So we can always use the number at List.size() / 2, as the meeting point.

28.01 %
class Solution {
    public int minTotalDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return -1;
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> xSet = new ArrayList<>();
        List<Integer> ySet = new ArrayList<>();
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (grid[x][y] == 1) {
                    xSet.add(x);
                    ySet.add(y);
                }
            }
        }
     
        int xMedian = xSet.get(xSet.size() / 2);
        Collections.sort(ySet);
        int yMedian = ySet.get(ySet.size() / 2);
        return sumUp(xSet, xMedian) + sumUp(ySet, yMedian);  
    }
    private int sumUp(List<Integer> set, int median) {
        int sum = 0;
        for (Integer n : set) {
            sum += Math.abs(n - median);
        }
        return sum;
    }
}
二刷
用了优化的方法，assume there's a median point but do not actually calculate it
After we sort the list, we know that the 1st half of points are less than the median point and the 2nd half of points are larger than the median point
Use the property that, for every pair of points in the list, diff = mid - start + end - mid = end - start
55.49 %

class Solution {
    public int minTotalDistance(int[][] grid) {
     
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        // Find the median of all x positions / all y positions
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> xValues = new ArrayList<>();
        List<Integer> yValues = new ArrayList<>();
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (grid[x][y] == 1) {
                    xValues.add(x);
                    yValues.add(y);
                }
            }
        }
        //xValues is already sorted
        Collections.sort(yValues);
        return countDiff(xValues) + countDiff(yValues);
     
    }
    private int countDiff(List<Integer> list) {
        int sum = 0;
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            sum += list.get(end--) - list.get(start++);
        }
        return sum;
    }
}

Version #2 no sorting

分两次扫描全图，第一次outer loop是x++，这样保证x是按顺序递增的

第二次outer loop是y++，保证y是按顺序递增的

就可以避免sorting

可以将time complexity从O(mnlog(mn)) 优化到O(mn)

看了discussion发现另外一个优化是用int array instead of array list, use two pointers instead of calculation of size / 2. 可以使运算速度变快

三刷

Runtime: 3 ms, faster than 71.47% of Java online submissions for Best Meeting Point.

Memory Usage: 38.4 MB, less than 85.05% of Java online submissions for Best Meeting Point.

class Solution {

    public int minTotalDistance(int[][] grid) {

        List<Integer> xs = new ArrayList<>();

        List<Integer> ys = new ArrayList<>();

        for (int i = 0; i < grid.length; i++) {

            for (int j = 0; j < grid[0].length; j++) {

                if (grid[i][j] == 1) {

                    // add the x value

                    xs.add(i);

                }

            }

        }

        for (int j = 0; j < grid[0].length; j++) {

            for (int i = 0; i < grid.length; i++) {

                if (grid[i][j] == 1) {

                    // add the y value

                    ys.add(j);

                }

            }

        }

        int dist = 0;

        // 0, 1 size = 2

        // i = 0

        for (int i = 0; i < xs.size() / 2; i++) {

            dist += xs.get(xs.size() - 1 - i) - xs.get(i);

        }

        for (int j = 0; j < ys.size() / 2; j++) {

            dist += ys.get(ys.size() - 1 - j) - ys.get(j);

        }

        return dist;

    }

}