发表于 | 浏览 次
字数统计: 1,632 | 阅读时长 ≈ 8

title: 【leetcode】sort
date: 2018-02-08 13:38:35
tags:

categories:

leetcode 排序相关问题

Largest Number

题目

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

给定数组返回由该数组构成的最大数字，返回string类型

思路

先把数字转化成字符串，然后按字符串顺序排序，这里有一个小技巧，判断字符串s1和s2谁应该放在前面时，比较s1+s2和s2+s1

代码

class Solution {
    public String largestNumber(int[] nums) {
        Comparator<String> cmp = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1 = o1+o2;
                String s2 = o2+o1;
                return s2.compareTo(s1);
            }
        };
        String[] strs = new String[nums.length];
        for(int i = 0;i < nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs,cmp);
        if(strs[0].equals("0")){
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < strs.length;i++){
            sb.append(strs[i]);
        }
        return sb.toString();
    }
}

Maximum Gap

题目

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

给定一个无序数组，返回数组中相邻元素（排序后）之差的最大值

复杂度要求：线性时间复杂度

分析

baseline：排序，计算相邻元素最大值，时间复杂度

优化：桶排序

  1. 确定数组中最大和最小元素max和min，数组中元素个数N
  2. 这N个数字的平均间隔为：avg = (max-min)/(N-1)，maxGap >= avg，所以我们令桶的大小int bucketSize = Math.max(1,(max - min) / (N-1)); 这样每一个桶内，元素的差值不会超过avg了，那么相邻元素之间的最大间隔一定在桶之间。
  3. 根据桶的大小，可以计算出桶的个数为int bucketNum = (max - min)/bucketSize + 1; ,
  4. 遍历数组中的元素，将元素放入对应的桶中，并维护每个桶的最大值和最小值
  5. 计算相邻桶的最小值和最大值的差，遇到桶中没有元素的跳过，取最大的差值即为所求。

代码

class Solution {
    public int maximumGap(int[] nums) {
        int N = nums.length;
        if(N <= 1){
            return 0;
        }
        if(N == 2){
            return Math.abs(nums[0] - nums[1]);
        }
        //查找nums中最大和最小值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int num : nums){
            min = Math.min(min,num);
            max = Math.max(max,num);
        }
        //maxGap > avg = (max-min)/(N-1);bucketSize = floor(max-min)/(N-1);
        int bucketSize = Math.max(1,(max - min) / (N-1));//桶大小
        //bucketNum = ceil (max-min)/bucketSize
        int bucketNum = (max - min)/bucketSize + 1;//桶个数
        //用于记录每个bucket中的最大和最小值
        int[] bucketMin = new int[bucketNum];
        for(int i = 0 ; i < bucketNum;i++){
            bucketMin[i] = -1;
        }
        int[] bucketMax = new int[bucketNum];
        for(int i = 0 ; i < bucketNum;i++){
            bucketMax[i] = -1;
        }
        for(int i = 0 ; i < nums.length;i++){
            if(bucketMin[(nums[i]-min)/bucketSize] == -1){
                bucketMin[(nums[i]-min)/bucketSize] = nums[i];
                bucketMax[(nums[i]-min)/bucketSize] = nums[i];
            }
            else if(nums[i] < bucketMin[(nums[i]-min)/bucketSize]){
                bucketMin[(nums[i]-min)/bucketSize] = nums[i];
            }
            else if(nums[i] > bucketMax[(nums[i]-min)/bucketSize]){
                bucketMax[(nums[i]-min)/bucketSize] = nums[i];
            }
        }
        int maxGap = 0;
        int lastMax =  bucketMax[0];
        for(int i = 1 ; i < bucketNum;i++){
            if(bucketMin[i] == -1){
                continue;
            }
            maxGap = Math.max(maxGap,bucketMin[i] - lastMax);
            lastMax = bucketMax[i];
        }
        return maxGap;
    }
}

Best Meeting Point

题目

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

> 1 - 0 - 0 - 0 - 1
> |   |   |   |   |
> 0 - 0 - 0 - 0 - 0
> |   |   |   |   |
> 0 - 0 - 1 - 0 - 0
>

>

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

给定二维数组，1代表n个人的出发地，0代表其余地点，找到数组中的一个位置，使得大家到这个地点的曼哈顿距离之和最短，返回最短距离

思路

只想到了暴力的思路。。。

看了solution，需要从一维的入手：

Case #1: 1-0-0-0-1
Case #2: 0-1-0-1-0
Case #3: 1-0-0-0-0-0-0-1-1
Case #4: 1-1-0-0-1

给了这么几个例子，说明到所有点最短的距离就是中位数的点。

所以扩展到二维，到所有点距离最短的点就是所有点分别在x轴和y轴中位数的点。

因此可以遍历所有的点，记录是1的点的xy坐标，然后分别对xy坐标排序，取中位数的点，即为要求的点，再计算下距离就好。

优化：

可以把横纵坐标分离计算，按需加入list,这样就不需要排序了,直接取中位数位置的点

代码

public class BestMeetingPoint {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        for(int i = 0 ; i < grid.length;i++){
            for(int j = 0 ; j <grid[0].length;j++){
                if(grid[i][j] == 1){
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        int num = rows.size()/2;
        Collections.sort(rows);
        Collections.sort(cols);
        int x = rows.get(num);
        int y = cols.get(num);
        int result = 0;
        for(int i = 0;i < rows.size();i++){
            result += Math.abs(x- rows.get(i));
            result += Math.abs(y- cols.get(i));
        }
        return result;
    }
}

Insert Interval

题目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

给定区间数组，区间之间没有overlap，又给定一个独立区间，将该独立区间加到数组的区间里，如有overlap将区间merge,返回加入独立区间后的数组

思路

  1. 遍历数组中的区间，当数组中的区间和独立区间还没有交集（intervals.get(i).end < newInterval.start）的时候，将这些区间原封不动放入result中
  2. 将区间start和end初始化为newInterval的start和end
  3. 继续遍历数组中的区间，直至intervals.get(i).start > newInterval.end,也就是和独立区间不相交了，在此期间，更新数组的上下边界
  4. 将更新好的区间加入结果
  5. 将剩余区间加入结果

代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class InsertInterval {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<>();
        int i = 0;
        while(i < intervals.size() && intervals.get(i).end < newInterval.start){
            res.add(intervals.get(i));
            i++;
        }
        if(i == intervals.size()){
            res.add(newInterval);
            return res;
        }
        int start = newInterval.start;
        int end = newInterval.end;
        while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
            start = Math.min(start,intervals.get(i).start);
            end = Math.max(end,intervals.get(i).end);
            i++;
        }
        res.add(new Interval(start,end));
        while(i < intervals.size()){
            res.add(intervals.get(i));
            i++;
        }
        return res;
    }
}

H-Index