2023-10-07：用go语言，给定n个二维坐标，表示在二维平面的n个点，坐标为double类型，精度最多小数点后两位，希

福大大架构师每日一题

发布于 2023-10-08 15:12:46

2370

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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