1. AI技术聚合首页
  2. IT

①归并排序、快速排序 、堆排序、计数排序[算法、代码模板、面试题]

心中带点小风骚 • • IT • 阅读 52

个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~
个人主页：.29.的博客
学习社区：进去逛一逛~

排序[算法、代码模板、面试题]

  • ①归并排序、快速排序 、堆排序、计数排序
    • 🚀归并排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀快速排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀堆排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀912. 排序数组
    • 🚀315. 计算右侧小于当前元素的个数
    • 🚀561. 数组拆分
    • 🚀1122. 数组的相对排序（计数排序）
    • 🚀268. 丢失的数字（计数排序）
    • 🚀215. 数组中的第K个最大元素
    • 🚀347. 前 K 个高频元素
    • 🚀LCR 159. 库存管理 III(计数排序)
    • 🚀LCR 170. 交易逆序对的总数

①归并排序、快速排序 、堆排序、计数排序

🚀归并排序

⚪步骤

归并排序：

归并排序是一种分治法（Divide and Conquer）的经典排序算法，它的基本思想是将原始数组划分成较小的数组，然后递归地对这些小数组进行排序，最后再将排好序的小数组合并成一个整体有序的数组。下面是**归并排序的详细过程： **



详细步骤：

分解（Divide）:

  • 将数组一分为二，找到中间位置。
  • 递归地对左右两个子数组进行分解，直到每个子数组只有一个元素。

排序（Conquer）：

  • 当每个子数组只包含一个元素时，认为它已经有序。

合并（Merge）：

  • 将两个有序的子数组合并成一个有序的数组。
  • 创建一个临时数组，依次比较两个子数组的元素，将较小的元素放入临时数组。
  • 如果其中一个子数组的元素已经全部放入临时数组，将另一个子数组的剩余部分直接放入临时数组。
  • 将临时数组复制回原始数组的相应位置，完成合并。



⚪实现

算法实现：

public class mergeSortTest {
	
	//main函数，用于测试
	public static void main(String[] args) {
		//手动创建数组
		int[] arr = new int[] {1,5,88,3,-8,7,256,-8,6,15,-96};
		//使用归并排序
		process(0,arr.length-1,arr);
		//遍历排序后数组
		for(int i = 0;i < arr.length;++i) {
			System.out.print(arr[i] + " ");
		}
	}

	//分解 + 合并（分解合并过程中已完成排序）：
	public static void process(int L, int R, int[] arr) {
		if(L == R) return;            //下标重合，结束
		int mid = L + ((R - L) >> 1); //获取中间下标mid、 (R - L) >> 1 等同于 (R - L) / 2
		process(L , mid, arr);        //分解左子数组
		process(mid + 1, R, arr);     //分解右子数组
		merge(L, mid, R, arr);        //合并
	}
	
	//合并：
	public static void merge(int L, int mid, int R, int[] arr) {
		int[] help = new int[R - L + 1];  //帮组数组
		int p1 = L;                       //左子数组起始下标
		int p2 = mid + 1;                 //右子数组起始下标
		int i = 0;                        //帮组数组起始下标
		
		//合并，两个子数组元素按顺序比较，较小的元素放入帮组数组，重复此步骤。
		while(p1 <= mid && p2 <= R) {
			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
		}
		while(p1 <= mid) {
			help[i++] = arr[p1++];
		}
		while(p2 <= R) {
			help[i++] = arr[p2++];
		}
		
		//将帮助数组的元素赋值回元素组。
		for(i = 0;i < help.length; ++i) {
			arr[i + L] = help[i];
		}
	}
	
}



⚪复杂度

复杂度分析：

  • 时间复杂度： O(n log n) – 归并排序始终都是O(n log n)的，无论最坏情况还是平均情况。
  • 空间复杂度： O(n) – 归并排序需要一个与原始数组同样大小的辅助数组来进行合并操作，因此空间复杂度为O(n)。


🚀快速排序

⚪步骤

快速排序：

快速排序（Quick Sort）是一种常用的基于分治思想的排序算法。它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录均比另一部分的记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心是选择一个基准元素，将小于等于基准的元素放在左边，大于基准的元素放在右边，然后对左右两个子序列分别递归地应用相同的方法。


详细步骤：

  1. 选择基准元素：
    • 从待排序数组中选择一个元素作为基准元素。通常选择第一个元素、最后一个元素或者中间元素。（本文等概率随机选取一个元素作为基准，避免最坏复杂度的发生）
  2. 分区（Partition）：
    • 将数组中小于等于基准的元素放在基准的左边，大于基准的元素放在右边。这一步通常称为分区操作。
    • 使用两个指针，一个在数组的起始位置，一个在数组的结束位置，分别向中间移动，交换不符合条件的元素，直到两个指针相遇。
  3. 递归排序：
    • 对基准左右两侧的子数组进行递归排序。重复以上步骤，直到每个子数组的大小为1或0。



⚪实现

算法实现：

public class Qsort {
    //main函数，用于测试
	public static void main(String[] args) {
		//手动创建数组，用于测试
		int[] arr = new int[] {1,5,99,-29,698,-111,0,63,88,3,3,7,1,-8,7,256};
		
		//若数组为空，长度<2等情况，无需排序
		if(arr == null || arr.length < 2) {
			return;
		}
		
		//使用快速排序，传入数组头部和尾部下标
		quickSort(0, arr.length-1, arr);
		for(int i = 0;i < arr.length;++i) {
			System.out.print(arr[i] + " ");
		}
	}
	
	//快速排序函数：
	public static void quickSort(int L, int R, int[] arr) {
		//下表不越界情况下：进行基准选取、划分、递归排序
		if(L < R) {
			//使用random函数，随机选取一个元素作为基准，使得复杂度总是O(n log n)
			swap(R, L + (int)(Math.random() * (R - L + 1)), arr);
			//进行划分，获取到两个边界值：小于基准的边界less，大于基准的边界more
			//p[0] = less + 1 ，p[1] = more - 1
			int[] p = partition(L, R, arr);
			//分别对划分后的子数组继续进行上述操作，是为递归排序
			quickSort(L, p[0] - 1, arr);
			quickSort(p[1] + 1, R, arr);
		}
	}
	
	//划分函数：
	public static int[] partition(int L, int R, int[] arr) {
		//定义小于基准的边界less，大于基准的边界more
		int less = L - 1;
		int more = R;
		//从数组起始下标L开始遍历，直到超过大于基准的边界more，即下标越界
		while(L < more) {
			//当前元素小于基准，与less边界外的元素交换，less边界扩展1位，下一元素作为当前元素
			if(arr[L] < arr[R]) {        
				swap(++less, L++, arr);
			//当前元素大于基准，与more边界外的元素交换，more边界扩展1位，交换后，当前元素未被比较，无需后移
			}else if(arr[L] > arr[R]) {
				swap(--more, L, arr);
			//等于基准，无需交换，直接后移
			}else {
				++L;
			}
		}
		//划分完成后，将数组末尾的基准元素与more边界位置元素交换，真正的more边界变为more + 1
		swap(more, R, arr);
		//将边界存入数组返回：
		return new int[] {less + 1, more};
	}
	
	//交换函数：
	public static void swap(int a, int b, int[] arr) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
    
}



⚪复杂度

复杂度分析：

  • 时间复杂度： 平均情况下为O(n log n)，最坏情况为O(n^2)。快速排序的性能高度依赖于选择的基准元素。
  • 空间复杂度： O(log n) – 快速排序是一种原地排序算法，只需要常数级别的额外空间用于递归调用的栈。


🚀堆排序

⚪步骤

堆排序：

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一个完全二叉树，可以分为最大堆和最小堆两种类型。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

以下是堆排序的详细步骤：


详细步骤：

  1. 建堆（Heapify）：
    • 将待排序的数组构建成一个堆。建堆的过程是从最后一个非叶子节点开始，依次向上调整各个子树，使其满足堆的性质。
  2. 排序：
    • 交换堆顶元素（最大或最小元素）和堆的最后一个元素，然后将堆的大小减 1。
    • 再次调整堆，使其满足堆的性质。
    • 重复上述步骤，直到堆的大小为 1，排序完成。



⚪实现

代码实现：

public class heapSortTest {
	//main函数、测试用
	public static void main(String[] args) {
		int[] arr = new int[]{1,5,88,9,-88,-99,-685,78,4,3,3,7,1,-8,7,256};
		heapSort(arr);
		for(int i = 0;i < arr.length;++i) {
			System.out.print(arr[i] + " ");
		}
	}
	
	// 堆排序，排序函数
	public static void heapSort(int[] arr) {
		if(arr == null || arr.length < 2) return;
		
		for(int i = arr.length - 1; i >= 0; --i) {
			heapify(arr, i, arr.length - 1);
		}
		
		int heapSize = arr.length;
		swap(arr, 0, --heapSize);
		
		while(heapSize > 0) {
			heapify(arr, 0, heapSize);
			swap(arr, 0, --heapSize);
		}
	}
	
	//heapify，建堆函数
	public static void heapify(int[] arr, int index, int heapSize) {
		//获取左孩子下标
		int left = 2 * index + 1;
		//left < heapSize : 当前节点存在左孩子
		while(left < heapSize) {
			// 获取左孩子、右孩子中最大值
			int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
			// 较大孩子元素与父节点元素比较，更新较大值下标
			largest = arr[index] < arr[largest] ? largest : index;
			// 父节点最大，无法下移，直接停止
			if(index == largest) break;
			// 父节点小于较大孩子，下移
			swap(arr, index, largest);
			// 维护父节点和左孩子
			index = largest;
			left = 2 * index + 1;
		}
	}
	
	//交换函数
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	
}



⚪复杂度

复杂度分析：

  • 时间复杂度： 建堆操作的时间复杂度为O(n)，排序操作的时间复杂度为O(n log n)。因此，堆排序的总体时间复杂度为O(n log n)。
  • 空间复杂度： 堆排序是一种原地排序算法，只需使用常数级别的额外空间，因此空间复杂度为O(1)。


🚀912. 排序数组

[⚪点击跳转【LeetCode 912. 排序数组】](912. 排序数组 – 力扣（LeetCode）)

题目：

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104



解法一：归并排序：

//使用归并排序
class Solution {
    public int[] sortArray(int[] nums) {
        int length = nums.length;
        mergeSort(nums,0,nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] arr,int l,int r){
        //子数组长度为1，停止
        if(l == r) return;
        //取中点
        int mid = l + ((r - l) >> 1);
        //递归排序左子数组
        mergeSort(arr,l,mid);
        //递归排序右子数组
        mergeSort(arr,mid + 1,r);
        //合并两个排序好的数组
        merge(arr,l,mid,r);
    }

    public void merge(int[] arr,int l,int mid,int r){
        //help数组
        int[] help = new int[r - l + 1];
        //help数组下标
        int i = 0;
        //左子数组头p1
        int p1 = l;
        //右子数组头p2
        int p2 = mid + 1;
        //合并两个有序数组，存入help数组
        while(p1 <= mid && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }

        //将help数组的元素赋值回目标数组
        for(int j = 0;j < help.length;++j){
            arr[l + j] = help[j];
        }

    }
}

解法二：快速排序：

class Solution {
    //快排
    public int[] sortArray(int[] nums) {
        if(nums == null || nums.length < 2) return nums; //空或长度1，无需排序

        qSort(nums,0,nums.length - 1); //快排

        return nums;
    }

    public static void qSort(int[] arr,int l,int r){
        //数组头尾不冲突
        if(l < r){
            //利用random等概率随机获取基准 与尾部元素交换位置
            swap(arr,r,l + (int)(Math.random() * (r - l + 1)));
            //得到长度二的数组，两个元素分别代表大于基准元素与小于基准元素的边界
            int[] p = partition(arr,l,r);
            qSort(arr,l,p[0]);
            qSort(arr,p[1],r);
        }
    }

    //划分函数
    public static int[] partition(int[] arr,int l,int r){
        int less = l - 1; //小于基准的边界
        int more = r;     //大于基准的边界
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr,++less,l++);
            }else if(arr[l] > arr[r]){
                swap(arr,--more,l);
            }else{
                ++l;
            }
        }
        swap(arr,more,r);
        return new int[]{less,more + 1};
    }

    //交换
    public static void swap(int[] arr,int a,int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

解法三：堆排序：

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public static void heapSort(int[] arr){
        if(arr == null || arr.length < 2) return;

        for(int i = arr.length - 1; i >= 0; --i){
            heapify(arr, i, arr.length);
        }

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);

        while(heapSize > 0){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    public static void heapify(int[] arr, int index, int heapSize){
        int left = 2 * index + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && arr[left] < arr[left+1] ? left + 1 : left;
            largest = arr[index] < arr[largest] ? largest : index;
            if(largest == index) break;
            swap(arr, index, largest);
            index = largest;
            left = 2 * index + 1;
        }
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}


🚀315. 计算右侧小于当前元素的个数

⚪点击跳转：315. 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104



利用归并排序性质，完成计数：

// 利用归并排序的特性， 计算 nums[i] 右侧小于 nums[i] 的元素的数量。
class Solution {
    static int[] counts; // 题目要求的counts数组
    static int[] index;  // 下标数组，记录nums元素的移动，即：元素移动，下标做同样操作。

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>(); //创建集合，因为:函数返回值为List<Integer>
        if(nums == null) return list;           //数组为空，直接返回空集合
        if(nums.length == 1){                   //数组长度=1
            list.add(0);      //右侧没有小于nums[i]的元素，所以nums[i]=0，添加到集合中
            return list;      //直接返回
        }

        //初始化counts和index
        int n = nums.length;
        this.counts = new int[n];
        this.index = new int[n];

        //为下标数组元素 附上 下标值
        for(int i = 0;i < n; ++i){
            index[i] = i;
        }

        //进行归并排序，在排序过程中完成计数
        mergeSort(nums, 0, n - 1);

        //将得到的符合规则的counts数组元素赋值给集合再返回，因为:函数返回值为List<Integer>
        for(int count : counts) list.add(count);
        return list;
    }

    //归并排序：
    public static void mergeSort(int[] arr, int l, int r){
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    //合并有序子序列
    public static void merge(int[] arr, int l, int mid, int r){
        int[] help = new int[r - l + 1];   //元素的help数组，用于合并有序子序列
        int[] helpI = new int[r - l + 1];  //下标的help数组，用于记录合并有序子序列时元素的移动
        int i = 0;        //下标
        int p1 = l;       //左子序列头元素下标
        int p2 = mid + 1; //右子序列头元素下标

        while(p1 <= mid && p2 <= r){
            //按照逆序，进行归并排序的合并
            if(arr[p1] > arr[p2]){
                //因为逆序，所以p2到R范围内的元素是降序的，即：
                //当前情况下nums[i] 右侧小于 nums[i] 的元素的数量 = r - p2 + 1
                //在排序过程中，累加所有情况下的r - p2 + 1，就能的到总数。
                counts[index[p1]] += r - p2 + 1;
                help[i] = arr[p1];
                helpI[i++] = index[p1++];
            }else{
                help[i] = arr[p2];
                helpI[i++] = index[p2++];
            }
        }
        while(p1 <= mid){
            help[i] = arr[p1];
            helpI[i++] = index[p1++];
        }
        while(p2 <= r){
            help[i] = arr[p2];
            helpI[i++] = index[p2++];
        }

        //将help数组中的元素 赋值回原数组中，完成合并。
        for(i = 0;i < help.length; ++i){
            arr[i + l] = help[i];
            index[i + l] = helpI[i];
        }
    }
}


🚀561. 数组拆分

⚪点击跳转：561. 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：

  • 1 <= n <= 104
  • nums.length == 2 * n
  • -104 <= nums[i] <= 104



题解（归并排序）：

//归并排序
class Solution {
    public int arrayPairSum(int[] nums) {
        //排序数组（这里使用归并排序，还推荐使用堆排序、快速排序）
        mergeSort(nums, 0, nums.length - 1);

        //根据分析，有序的数组分成n对，就能满足题意
        int ans = 0;
        for(int i = 0;i < nums.length; i += 2){
            //将每队的min(ai, bi)累加起来，得到总和
            ans += nums[i];
        }

        //返回结果
        return ans;
    }

    public static void mergeSort(int[] arr, int l, int r){
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l,int mid, int r){
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = mid + 1;
        int i = 0;

        while(p1 <= mid && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }

        for(i = 0;i < help.length; ++i){
            arr[i + l] = help[i];
        }
    }
}



题解（堆排序）：

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length;
        heapSort(nums, n); //堆排序

        int ans = 0;
        for(int i = 0;i < n; i += 2){
            ans += nums[i];
        }

        return ans;
    }

    public static void heapSort(int[] arr, int n){
        if(arr == null || n < 2) return;

        for(int i = n - 1; i >= 0; --i){
            heapify(arr, i, n);
        }

        int heapSize = n;
        swap(arr, 0, --heapSize);

        while(heapSize > 0){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    public static void heapify(int[] arr, int index, int heapSize){
        int left = 2 * index + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[index] > arr[largest] ? index : largest;
            if(index == largest) break; //无法下移，停止
            swap(arr, index, largest);  //可以下移，交换
            index = largest;            //交换完后完成下移
            left = 2 * index + 1;       //维护左孩子
        }
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}



题解（快速排序）【速度最快】：

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length;
        quickSort(nums, 0, n - 1);

        int ans = 0;
        for(int i = 0;i < n; i += 2){
            ans += nums[i];
        }

        return ans;
    }

    public static void quickSort(int[] arr, int l, int r){
        if(l < r){
            swap(arr, r, l + (int)(Math.random() * (r - l + 1)));
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0]);
            quickSort(arr,p[1], r);
        }
    }

    public static int[] partition(int[] arr, int l, int r){
        int less = l - 1;
        int more = r;
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr, ++less, l++);
            }else if(arr[l] > arr[r]){
                swap(arr, --more, l);
            }else{
                ++l;
            }
        }
        swap(arr, more, r);
        return new int[]{less, more + 1};
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}


🚀1122. 数组的相对排序（计数排序）

⚪点击跳转：1122. 数组的相对排序

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

示例 2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

提示：

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i] 各不相同
  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中



题解（计数排序）：

计数排序是一种非比较性的整数排序算法，适用于待排序元素的范围较小的情况。该算法的基本思想是统计每个元素的出现次数，然后根据这些统计信息将元素放回正确的位置。

class Solution {
    //计数排序
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //题目给定元素大小不超过1000，就可以设置一个1001长度的数组来进行计数排序
        int[] arr = new int[1001];         //计数数组
        int[] ans = new int[arr1.length];  //排序数组
        int index = 0;                     //排序数组的下标

        //遍历arr1，遍历到元素，就使arr数组对应下标的值+1
        for(int num : arr1){
            arr[num] += 1;
        }

        //遍历arr2数组，先将与arr2相对顺序元素放入排序数组
        for(int num : arr2){
            for(int i = 0;i < arr[num]; ++i){
                ans[index++] = num;
            }
            arr[num] = 0; //维护计数数组
        }

        //遍历计数数组，将剩下的元素排序好并放入排序数组
        for(int k = 0;k < 1001; ++k){
            for(int i = 0;i < arr[k]; ++i){
                ans[index++] = k;
            }
        }
        
        return ans;
    }
}


🚀268. 丢失的数字（计数排序）

⚪点击跳转：268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二



题解（计数排序）

class Solution {
    public int missingNumber(int[] nums) {
        int ans = -1;               //没有出现在数组中的那个数。
        int n = nums.length;        //题目提到的n
        int[] arr = new int[n + 1]; //计数数组，用于记录元素出现的次数
        for(int num : nums){        //使用计数数组，记录并排序nums数组元素
            arr[num] += 1;
        }
        for(int i = 0;i <= n; ++i){ //遍历计数数组，值为0表示未出现
            if(arr[i] == 0){
                ans = i;
                break;
            }
        }
        return ans;
    }
}


🚀215. 数组中的第K个最大元素

⚪点击跳转：215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104



题解（快速排序）：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);

        int ans = Integer.MIN_VALUE;
        for(int i = 0;i <= nums.length - k; ++i){
            ans = nums[i];
        }

        return ans;
    }

    public static void quickSort(int[] arr, int l, int r){
        if(l < r){
            swap(arr, r, l + (int)(Math.random() * (r - l)));
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0]);
            quickSort(arr, p[1], r);
        }
    }

    public static int[] partition(int[] arr, int l, int r){
        int less = l - 1;
        int more = r;
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr, ++less, l++);
            }else if(arr[l] > arr[r]){
                swap(arr, --more, l);
            }else{
                ++l;
            }
        }
        swap(arr, more, r);
        return new int[]{less, more + 1};
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}


🚀347. 前 K 个高频元素

⚪点击跳转：347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的



题解（优先队列[堆排序] + hash表）：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[1] - a[1]));
        Map<Integer, Integer> map = new HashMap<>();
        int[] ans = new int[k];

        for(int num : nums){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else{
                map.put(num,map.get(num).intValue() + 1);
            }
        }

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            pq.offer(new int[]{entry.getKey(), entry.getValue()});
        }

        for(int i = 0;i < k; ++i){
            ans[i] = pq.poll()[0];
        }

        return ans;
    }
}


🚀LCR 159. 库存管理 III(计数排序)

⚪点击跳转：LCR 159. 库存管理 III

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

提示：

  • 0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000



题解（计数排序）：

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int[] help = new int[10001];

        for(int num : stock){
            help[num] += 1;
        }

        int[] ans = new int[cnt];
        int index = 0;
        a:for(int i = 0;i < 10001; ++i){
            for(int j = 0;j < help[i]; ++j){
                if(index < cnt){
                    ans[index++] = i;
                }else{
                    break a;
                }
            }
        }

        return ans;
    }
}



题解（快速排序）：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        qSort(arr,0,arr.length - 1);
        for(int i = 0;i < k;++i){
            ans[i] = arr[i];
        }
        return ans;
    }

    public static void qSort(int[] arr,int l,int r){
        if(l < r){
            swap(arr,r,l + (int)(Math.random() * (r - l + 1)));
            int[] p = partition(arr,l,r);
            qSort(arr,l,p[0]-1);
            qSort(arr,p[1]+1,r);
        }
    }

    public static int[] partition(int[] arr,int l,int r){
        int less = l - 1;
        int more = r;
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr,++less,l++);
            }else if(arr[l] > arr[r]){
                swap(arr,l,--more);
            }else{
                ++l;
            }
        }
        swap(arr,r,more);
        return new int[]{less+1,more};
    }

    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}


🚀LCR 170. 交易逆序对的总数

⚪点击跳转：LCR 170. 交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1:

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

限制：

0 <= record.length <= 50000



归并排序 题解：

class Solution {
    int ans = 0;
    public int reversePairs(int[] record) {
        if(record == null || record.length < 2) return ans;
        mergeSort(record, 0, record.length - 1);
        return ans;
    }

    public void mergeSort(int[] arr, int l, int r){
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public void merge(int[] arr, int l, int mid, int r){
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = mid + 1;
        int i = 0;
        while(p1 <= mid && p2 <= r){
            if(arr[p1] > arr[p2]){
                ans += r - p2 + 1;
                help[i++] = arr[p1++];
            }else{
                help[i++] = arr[p2++];
            }
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }

        for(i = 0;i < help.length; ++i){
            arr[i + l] = help[i];
        }
    }
}



文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2023年12月27日
下一篇 2023年12月27日

相关推荐