2023-10-07：用 go 语言，给定 n 个二维坐标，表示在二维平面的 n 个点，
坐标为 double 类型，精度最多小数点后两位，
希望在二维平面上画一个圆，圈住其中的 k 个点，其他的 n-k 个点都要在圆外。
返回一个圆心和半径，表示哪个圆可以圈住其中的 k 个点。
坐标和半径都是 double 类型，最多保留小数点后两位。
下面是正式题目，
给你一个整数数组 arr 和一个整数 k，
现需要从数组中恰好移除 k 个元素。
请找出移除后数组中不同整数的最少数目。
输入：arr = [4,3,1,1,3,3,2], k = 3。
输出：2。
来自美团面试题。
来自左程云。
答案 2023-10-07：
大体步骤如下：
1.创建一个 map m，用于存储数组 arr 中每个整数出现的次数。
2.遍历数组 arr，统计每个整数出现的次数，并保存在 map m 中。
3.创建一个数组 cnts，用于存储 map m 中的值（即整数出现的次数）。
4.将 cnts 数组排序，以便移除出现次数少的整数。
5.初始化一个变量 i 为 0，用于记录已移除的整数个数。
6.遍历排序后的 cnts 数组：
减去当前整数出现的次数 k，并将结果保存在变量 k 中。
如果 k 小于等于 0，说明已经移除了足够的整数，退出循环。
如果 k 等于 0，说明恰好移除了整数的次数，将变量 i 加 1。
7.返回剩下的整数个数，即 len(cnts)减去已移除的整数个数 i。
总的时间复杂度为 O(nlogn)，其中 n 为数组 arr 的长度，主要消耗在排序 cnts 数组上。额外空间复杂度为 O(n)，用于存储 map m 和数组 cnts。
go 完整代码如下：
package main
import ( "fmt" "sort")
func findLeastNumOfUniqueInts(arr []int, k int) int { m := make(map[int]int) for _, num := range arr { m[num]++ } cnts := make([]int, 0, len(m)) for _, cnt := range m { cnts = append(cnts, cnt) } sort.Ints(cnts) i := 0 for ; i < len(cnts); i++ { k -= cnts[i] if k <= 0 { if k == 0 { i++ } break } } return len(cnts) - i}
func main() { arr := []int{4, 3, 1, 1, 3, 3, 2} k := 3 result := findLeastNumOfUniqueInts(arr, k) fmt.Println(result)}
复制代码
rust 完整代码如下：
use std::collections::HashMap;
fn find_least_num_of_unique_ints(arr: Vec<i32>, mut k: i32) -> i32 { let mut map: HashMap<i32, i32> = HashMap::new(); for num in arr { let count = map.entry(num).or_insert(0); *count += 1; } let n = map.len(); let mut cnts: Vec<i32> = Vec::with_capacity(n); for &cnt in map.values() { cnts.push(cnt); } cnts.sort(); let mut i = 0; for cnt in &cnts { k -= cnt; if k <= 0 { if k == 0 { i += 1; } break; } i += 1; } (n - i) as i32}
fn main() { let arr = vec![4, 3, 1, 1, 3, 3, 2]; let k = 3; let result = find_least_num_of_unique_ints(arr, k); println!("{}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <unordered_map>#include <algorithm>
int findLeastNumOfUniqueInts(std::vector<int>& arr, int k) { std::unordered_map<int, int> map; for (int num : arr) { map[num]++; }
int n = map.size(); std::vector<int> cnts; for (auto& pair : map) { cnts.push_back(pair.second); } std::sort(cnts.begin(), cnts.end());
int i = 0; for (i = 0; i < n; i++) { k -= cnts[i]; if (k <= 0) { if (k == 0) { i++; } break; } } return n - i;}
int main() { std::vector<int> arr = { 4, 3, 1, 1, 3, 3, 2 }; int k = 3; int result = findLeastNumOfUniqueInts(arr, k); std::cout << result << std::endl; return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
typedef struct { int key; int value;} Pair;
int compare(const void* a, const void* b) { return ((Pair*)a)->value - ((Pair*)b)->value;}
int findLeastNumOfUniqueInts(int* arr, int arrSize, int k) { Pair* map = (Pair*)malloc(arrSize * sizeof(Pair)); int size = 0;
for (int i = 0; i < arrSize; i++) { int key = arr[i]; int found = 0;
for (int j = 0; j < size; j++) { if (map[j].key == key) { map[j].value++; found = 1; break; } }
if (!found) { map[size].key = key; map[size].value = 1; size++; } }
qsort(map, size, sizeof(Pair), compare); int i = 0; for (; i < size; i++) { k -= map[i].value; if (k <= 0) { if (k == 0) { i++; } break; } }
free(map);
return size - i;}
int main() { int arr[] = { 4, 3, 1, 1, 3, 3, 2 }; int arrSize = sizeof(arr) / sizeof(arr[0]); int k = 3; int result = findLeastNumOfUniqueInts(arr, arrSize, k); printf("%d\n", result);
return 0;}
复制代码
评论