首页 > 分享 > 笔试题2019/8/29

笔试题2019/8/29

花匠小妙招
2024-12-03 16:12

题目描述自己的思路先，捋一遍，我们得到的数组是排序好的从这个数组中找到最靠近x的k个数，返回结果升序。额外条件，如果两个数值和x差一样，优先选择较小的数字
直接贴代码：

import java.util.*; public class Main1 { public static int count=0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] ss = sc.nextLine().split(","); int[] arr = new int[ss.length]; for (int i = 0; i < ss.length; i++) { arr[i] = Integer.valueOf(ss[i]); } count= sc.nextInt(); int num = sc.nextInt(); int[] abs=new int[arr.length]; for (int i = 0; i <arr.length ; i++) { abs[i]=Math.abs(arr[i]-num); } // 得到和目标的abs数组 // 找到abs数组中距离参考值num 最小的count个值，返回一个set，因为大概率会有重复abs值 HashSet kthNumbers = findKthNumbers(abs, abs.length, count); // 定义一个结果数组 List resultlist = new ArrayList(); // 再回过头去找对应arr里面的原来的数字 for (int i : arr) { if(kthNumbers.contains(Math.abs(i-num))){ // 将所有满足要求的arr 里面的数字添加到resultlist当中，这个list 的长度可能大于cout的值下一步进一步优化 resultlist.add(i); } } ArrayList result = delete((ArrayList) resultlist); Iterator iterator = result.iterator(); while (iterator.hasNext()){ System.out.print(iterator.next()); if (iterator.hasNext()){ System.out.print(","); } } } public static HashSet findKthNumbers(int[] A, int n, int k) {//找到这个数组中最小的k个值，可重复 int count = n - k; int length = A.length; while (count > 0) { int maxNumberIndex = 0; int i; for (i = 1; i < length; i++) { if (A[maxNumberIndex] < A[i]) { maxNumberIndex = i; } } for (int j = maxNumberIndex; j < length - 1; j++) { A[j] = A[j + 1]; } length--; count--; } HashSet result = new HashSet(); for (int i = 0; i < length; i++) { result.add(A[i]); } return result; } public static ArrayList delete(ArrayList list){ //递归删除，如果长度大于count就从尾部删除 if(list.size()>count){ list.remove(list.size()-1); delete(list); } return list; } }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172

数据写入：
在这里插入图片描述

int[] abs=new int[arr.length]; for (int i = 0; i <arr.length ; i++) { abs[i]=Math.abs(arr[i]-num); } // 得到和目标的abs数组 // 找到abs数组中距离参考值num 最小的count个值，返回一个set，因为大概率会有重复abs值 123456

abs数组中存储的是初始数组中距离目标整数的差的绝对值，下标和原来的一致

HashSet kthNumbers = findKthNumbers(abs, abs.length, count); public static HashSet findKthNumbers(int[] A, int n, int k) {//找到这个数组中最小的k个值，可重复 int count = n - k; int length = A.length; while (count > 0) { int maxNumberIndex = 0; int i; for (i = 1; i < length; i++) { if (A[maxNumberIndex] < A[i]) { maxNumberIndex = i; } } for (int j = maxNumberIndex; j < length - 1; j++) { A[j] = A[j + 1]; } length--; count--; } HashSet result = new HashSet(); for (int i = 0; i < length; i++) { result.add(A[i]); } return result; }

123456789101112131415161718192021222324

findKthNumbers 这个函数的作用是找出数组中最小的k个数字
返回值放入一个set 集合中，因为set集合不可重复

List resultlist = new ArrayList(); // 再回过头去找对应arr里面的原来的数字 for (int i : arr) { if(kthNumbers.contains(Math.abs(i-num))){ // 将所有满足要求的arr 里面的数字添加到resultlist当中，这个list 的长度可能大于cout的值下一步进一步优化 resultlist.add(i); } } 12345678

定义一个结果list存放所有符合要求的arr 中的数，因为arr 是排序好的，所以list中的顺序也是排序好的。没什么问题
但是，可能会出现list 的长度过长的可能性
这个时候最后一步：

ArrayList result = delete((ArrayList) resultlist); Iterator iterator = result.iterator(); while (iterator.hasNext()){ System.out.print(iterator.next()); if (iterator.hasNext()){ System.out.print(","); } } public static ArrayList delete(ArrayList list){ //递归删除，如果长度大于count就从尾部删除 if(list.size()>count){ list.remove(list.size()-1); delete(list); } return list; }

12345678910111213141516

我们递归删除这个list 元素的末尾元素直到list 的长度等于目标长度
最后打印输出。
这个方法有点蠢… 想了下还是写出来，下面帖一个比较省事的方法