leetcode1481 java

java"/>

leetcode1481 java

目录

题目内容

代码部分

我的思路

题目内容

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

来源：力扣（LeetCode）
 

代码部分

class Solution {public int findLeastNumOfUniqueInts(int[] arr, int k) {Arrays.sort(arr);int a[];if(arr.length - 1==0) {a = new int[]{1};}else {a = new int[arr.length];}int t=0,sum=1;for (int i=1;i<arr.length;i++){if(arr[i-1]==arr[i]){sum++;}else {a[t]=sum;t++;sum=1;}}a[t]=sum;Arrays.sort(a);sum=0;t=arr.length>0?t+1:t;int all=t;t=0;for (int i=0;i<a.length;i++){if(a[i]!=0) {if (sum + a[i] <= k) {sum += a[i];t++;} else {break;}}}return all-t;}
}

我的思路

看到题目的第一反应是桶排序，但是马上就排除了这种方法，因为太浪费内存了。于是就想到再创建一个数组用来存放不同数字的数量。