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;
}
