Tag: 排序

解法一：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        HashMap<Integer,Integer> map = new HashMap();
        Arrays.sort(nums);
        if(nums[0] == 0 && nums[nums.length-1] == 0){
            List list = new ArrayList();
            list.add(0);
            list.add(0);
            list.add(0);
            res.add(list);
            return res;
        }
        if(nums[0] > 0 || nums[nums.length-1] < 0){
            return res;
        }
        for(int i = 0;i < nums.length-2;i++){
            if(nums[i] > 0){
                break;
            }
            if(i > 0 && (nums[i] == nums[i-1])){
                continue;
            }
            int target = -nums[i];
            map.clear();
            map.put(nums[i+1],i+1);
            for(int j = i+2;j < nums.length;j++){
                if(map.containsKey(target-nums[j])){
                    int k = map.get(target-nums[j]);
                    List list = new ArrayList(3);
                    list.add(nums[k]);
                    list.add(nums[j]);
                    list.add(nums[i]);
                    Collections.sort(list);
                    res.add(list);
                }
                map.put(nums[j],j);
            }
        }
        for(int i = 0;i < res.size()-1;i++){
            for(int j = i + 1;j < res.size();j++){
                if(res.get(i).equals(res.get(j))){
                    res.remove(j);
                    j--;
                }
            }
        }
        return res;
    }
}

T4mako4/17/26About 3 min

016_最接近的三数之和

解法一：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int res = 65535,sum;
        Arrays.sort(nums);
        int len = nums.length;
        int left,right;
        for (int i = 0; i < len - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            left = i + 1;
            right = len - 1;
            while(left < right){
                sum = nums[i] + nums[left] + nums[right];
                if(sum == target){
                    return target;
                }
                if(left + 1 == right){
                    res = Math.abs(res - target) > Math.abs(sum - target) ? sum : res;
                    break;
                }
                int leftSum = Math.abs((nums[i] + nums[left + 1] + nums[right]) - target);
                int rightSum = Math.abs((nums[i] + nums[left] + nums[right - 1]) - target);
                int abs = Math.abs(sum - target);
                if(leftSum <= abs && leftSum <= rightSum){
                    left++;
                }else if(rightSum <= abs && rightSum <= leftSum){
                    right--;
                }else{
                    res = Math.abs(res - target) > Math.abs(sum - target) ? sum : res;
                    break;
                }
            }
        }
        return res;
    }
}

T4mako4/17/26About 1 min

018_四数之和

解法一：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        int i,j,left,right;
        long tar;
        for (i = 0; i < len - 3; i++) {
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(j = i + 1;j < len - 2;j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                tar = target - (long)nums[i] - (long)nums[j];
                left = j + 1;
                right = len - 1;
                while(left < right){
                    if(nums[left] + nums[right] < tar){
                        left++;
                    }else if(nums[left] + nums[right] > tar){
                        right--;
                    }else {
                        ArrayList<Integer> temp = new ArrayList();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[left]);
                        temp.add(nums[right]);
                        res.add(temp);
                        while(left < len - 2 && nums[left] == nums[left + 1]){
                            left++;
                        }
                        left++;
                        while(right > j - 1 && nums[right] == nums[right-1]){
                            right--;
                        }
                        right--;
                    }
                }

            }
        }
        return res;
    }
}

T4mako4/17/26About 2 min

049_字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String,Integer> map = new HashMap<>();
        for (String str : strs) {
            String temp = sort(str);
            if (!map.containsKey(temp)) {
                List<String> list = new ArrayList<>();
                list.add(str);
                res.add(list);
                map.put(temp, res.size() - 1);
            } else {
                res.get(map.get(temp)).add(str);
            }
        }
        return res;
    }
   public String sort(String s){
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }
}

T4mako4/17/26Less than 1 minute

75. 颜色分类

题目描述

解法思路：选择排序

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        l = len(nums)
        for i in range(l):
            min_idx = i
            for j in range(i + 1,l):
                if nums[j] < nums[min_idx]:
                    min_idx = j
            nums[i], nums[min_idx] = nums[min_idx], nums[i]  # 交换最小值到当前位置

T4mako9/4/24Less than 1 minute

242. 有效的字母异位词

题目描述

class Solution {
    public boolean isAnagram(String s, String t) {
		if(s.length() != t.length()) return false;
		int len = s.length();
		int[] num1 = new int[26];
		int[] num2 = new int[26];
		for(int i = 0;i < len;i++) {
			num1[s.charAt(i) - 97]++;
			num2[t.charAt(i) - 97]++;
		}
		for(int i = 0;i < 26;i++) {
			if(num1[i] != num2[i]) return false;
		}
		return true;
    }
}

T4mako3/14/24Less than 1 minute

274. H 指数

题目描述

解法思路：逆序排序，遍历，比较遍历的值与下标的值

class Solution {
    public int hIndex(int[] citations) {
        int res = 1;
        Arrays.sort(citations);
        for(int i = citations.length - 1;i >= 0;i--){
            if(citations[i] >= res){
                res++;
            }else{
                return --res;
            }
        }
        return citations.length;
    }
}

T4mako2/20/24Less than 1 minute

2542. 最大子序列的分数

题目描述

解法思路：

根据 nums[2] 排序，同时根据更改的下标更新 nums[1]
建立小根堆，

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[]{nums1[i], nums2[i]};
        }
        Arrays.sort(arr, (a, b) -> (b[1] - a[1]));
        PriorityQueue<Integer> pq = new PriorityQueue();
        long res = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i][0];
            pq.offer(arr[i][0]);
            if (pq.size() == k) {
                res = Math.max(res, sum * arr[i][1]);
                sum -= pq.poll();
            }
        }
        return res;
    }
}

T4mako1/5/24Less than 1 minute

452. 用最少数量的箭引爆气球

题目描述

解法思路：

通过对每个数组左右端点进行排序
比较出每个区间的公共子区间，如果没有则 +1

class Solution {
    public int findMinArrowShots(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int len = intervals.length;
        // 根据每个数组第一个元素优先排序，再根据第二个元素排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                // 首先按照每个数组的第一个元素进行比较
                int compareFirstElement = Integer.compare(a[0], b[0]);
                if (compareFirstElement != 0) {
                    return compareFirstElement;
                } else {
                    // 如果第一个元素相同，则按照第二个元素进行比较
                    return Integer.compare(a[1], b[1]);
                }
            }
        });
        int res = 1;
        int[] temp = intervals[0]; // 记录公共子区间
        for (int i = 1; i < len; i++) {
            if(!(temp[1] < intervals[i][0])){ // 更新子区间
                temp[0] = Math.max(temp[0],intervals[i][0]);
                temp[1] = Math.min(temp[1],intervals[i][1]);
            }else{
                res++;
                temp = intervals[i];
            }
        }
        return res;
    }
}

T4mako1/2/24Less than 1 minute

2300. 咒语和药水的成功对数

题目描述

解题思路：
将 spells 数组排序，再遍历 potions 数组，在 spells 数组中找到第一个与 potions[i] 相乘大于等于 success 的位置

T4mako8/30/23Less than 1 minute