找到至少出现 k 次的最小整数
Finding the smallest integer that appears at least k times
给你一个整数数组A和一个整数k。实现一种算法，在线性时间内确定在 A 中至少出现 k 次的最小整数。
我一直在为这个问题苦苦挣扎一段时间，在Java中编码，我需要使用HashTable来找到至少出现k次的最小整数，它也必须是线性时间。
这是我尝试过的，但没有通过任何测试
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
if (k <= table.get(arr[i])) {
ans = Math.min(ans, arr[i]);
}
}else{
table.put(arr[i], 1);
}
}
return ans;
}
这是包含所有测试用例的空代码：
import java.io.*;
import java.util.*;
public class Lab5
{
/**
* Problem 1: Find the smallest integer that appears at least k times.
*/
private static int problem1(int[] arr, int k)
{
// Implement me!
return 0;
}
/**
* Problem 2: Find two distinct indices i and j such that A[i] = A[j] and |i - j| <= k.
*/
private static int[] problem2(int[] arr, int k)
{
// Implement me!
int i = -1;
int j = -1;
return new int[] { i, j };
}
// ---------------------------------------------------------------------
// Do not change any of the code below!
private static final int LabNo = 5;
private static final String quarter = "Fall 2020";
private static final Random rng = new Random(123456);
private static boolean testProblem1(int[][] testCase)
{
int[] arr = testCase[0];
int k = testCase[1][0];
int answer = problem1(arr.clone(), k);
Arrays.sort(arr);
for (int i = 0, j = 0; i < arr.length; i = j)
{
for (; j < arr.length && arr[i] == arr[j]; j++) { }
if (j - i >= k)
{
return answer == arr[i];
}
}
return false; // Will never happen.
}
private static boolean testProblem2(int[][] testCase)
{
int[] arr = testCase[0];
int k = testCase[1][0];
int[] answer = problem2(arr.clone(), k);
if (answer == null || answer.length != 2)
{
return false;
}
Arrays.sort(answer);
// Check answer
int i = answer[0];
int j = answer[1];
return i != j
&& j - i <= k
&& i >= 0
&& j < arr.length
&& arr[i] == arr[j];
}
public static void main(String args[])
{
System.out.println("CS 302 -- " + quarter + " -- Lab " + LabNo);
testProblems(1);
testProblems(2);
}
private static void testProblems(int prob)
{
int noOfLines = prob == 1 ? 100000 : 500000;
System.out.println("-- -- -- -- --");
System.out.println(noOfLines + " test cases for problem " + prob + ".");
boolean passedAll = true;
for (int i = 1; i <= noOfLines; i++)
{
int[][] testCase = null;
boolean passed = false;
boolean exce = false;
try
{
switch (prob)
{
case 1:
testCase = createProblem1(i);
passed = testProblem1(testCase);
break;
case 2:
testCase = createProblem2(i);
passed = testProblem2(testCase);
break;
}
}
catch (Exception ex)
{
passed = false;
exce = true;
}
if (!passed)
{
System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : ""));
passedAll = false;
break;
}
}
if (passedAll)
{
System.out.println("All test passed.");
}
}
private static int[][] createProblem1(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 5;
int[] numbers = getRandomNumbers(size, size);
Arrays.sort(numbers);
int maxK = 0;
for (int i = 0, j = 0; i < size; i = j)
{
for (; j < size && numbers[i] == numbers[j]; j++) { }
maxK = Math.max(maxK, j - i);
}
int k = rng.nextInt(maxK) + 1;
shuffle(numbers);
return new int[][] { numbers, new int[] { k } };
}
private static int[][] createProblem2(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 5;
int[] numbers = getRandomNumbers(size, size);
int i = rng.nextInt(size);
int j = rng.nextInt(size - 1);
if (i <= j) j++;
numbers[i] = numbers[j];
return new int[][] { numbers, new int[] { Math.abs(i - j) } };
}
private static void shuffle(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
int rndInd = rng.nextInt(arr.length - i) + i;
int tmp = arr[i];
arr[i] = arr[rndInd];
arr[rndInd] = tmp;
}
}
private static int[] getRandomNumbers(int range, int size)
{
int numbers[] = new int[size];
for (int i = 0; i < size; i++)
{
numbers[i] = rng.nextInt(2 * range) - range;
}
return numbers;
}
}
private static int problem1(int[] arr, int k) {
// Implement me!
Map<Integer, Integer> table = new TreeMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if (table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
} else {
table.put(arr[i], 1);
}
}
for (Map.Entry<Integer,Integer> entry : table.entrySet()) {
//As treemap is sorted, we return the first key with value >=k.
if(entry.getValue()>=k)
return entry.getKey();
}
//Not found
return -1;
}
正如其他人所指出的，有一些错误。首先，初始化 ans,
的行
int ans = 0;
您应该将 ans 初始化为 Integer.MAX_VALUE 以便当您发现一个整数首次出现至少 k 次时 ans 被设置为该整数适当的整数。其次，在您的 for 循环中，没有理由在迭代数组时跳过第一个元素，因此 i 应该初始化为 0 而不是 1。此外，在同一行中，您想要遍历整个数组，并且在您的循环条件下，当 k 不是数组的长度时，您现在有 i < k 。数组的长度由 arr.length 表示，因此条件应该改为 i < arr.length。三、这一行，
if (k < table.get(arr[i])){
在遍历数组时尝试检查一个整数到目前为止是否在数组中至少出现 k 次，< 运算符应更改为 <= 因为这里的关键词是至少k次，而不是“超过k次”。第四，k永远不要改变，这样你就可以摆脱这行代码，
k = table.get(arr[i]);
应用所有这些更改后，您的函数应如下所示：
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
if (k <= table.get(arr[i])) {
ans = Math.min(ans, arr[i]);
}
}else{
table.put(arr[i], 1);
}
}
return ans;
}
伪代码：
- 收集
Map<Integer, Integer>（数字及其计数） 中每个数字的频率
- 将最小值设置为较大的值
- 遍历条目
- 如果条目的值小于
k ，则忽略条目
- 如果entry key小于当前的least，存储为least
- return最少
一行实现：
private static int problem1(int[] arr, int k) {
return Arrays.stream(arr).boxed()
.collect(groupingBy(identity(), counting()))
.entrySet().stream()
.filter(entry -> entry.getValue() >= k)
.map(Map.Entry::getKey)
.reduce(MAX_VALUE, Math::min);
}
这样就可以过关了！感谢所有帮助过的人！！
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
}else{
table.put(arr[i], 1);
}
}
Set<Integer> keys = table.keySet();
for(int i : keys){
if(table.get(i) >= k){
ans = Math.min(ans,i);
}
}
if(ans != Integer.MAX_VALUE){
return ans;
}else{
return 0;
}
}
给你一个整数数组A和一个整数k。实现一种算法，在线性时间内确定在 A 中至少出现 k 次的最小整数。
我一直在为这个问题苦苦挣扎一段时间，在Java中编码，我需要使用HashTable来找到至少出现k次的最小整数，它也必须是线性时间。
这是我尝试过的，但没有通过任何测试
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
if (k <= table.get(arr[i])) {
ans = Math.min(ans, arr[i]);
}
}else{
table.put(arr[i], 1);
}
}
return ans;
}
这是包含所有测试用例的空代码：
import java.io.*;
import java.util.*;
public class Lab5
{
/**
* Problem 1: Find the smallest integer that appears at least k times.
*/
private static int problem1(int[] arr, int k)
{
// Implement me!
return 0;
}
/**
* Problem 2: Find two distinct indices i and j such that A[i] = A[j] and |i - j| <= k.
*/
private static int[] problem2(int[] arr, int k)
{
// Implement me!
int i = -1;
int j = -1;
return new int[] { i, j };
}
// ---------------------------------------------------------------------
// Do not change any of the code below!
private static final int LabNo = 5;
private static final String quarter = "Fall 2020";
private static final Random rng = new Random(123456);
private static boolean testProblem1(int[][] testCase)
{
int[] arr = testCase[0];
int k = testCase[1][0];
int answer = problem1(arr.clone(), k);
Arrays.sort(arr);
for (int i = 0, j = 0; i < arr.length; i = j)
{
for (; j < arr.length && arr[i] == arr[j]; j++) { }
if (j - i >= k)
{
return answer == arr[i];
}
}
return false; // Will never happen.
}
private static boolean testProblem2(int[][] testCase)
{
int[] arr = testCase[0];
int k = testCase[1][0];
int[] answer = problem2(arr.clone(), k);
if (answer == null || answer.length != 2)
{
return false;
}
Arrays.sort(answer);
// Check answer
int i = answer[0];
int j = answer[1];
return i != j
&& j - i <= k
&& i >= 0
&& j < arr.length
&& arr[i] == arr[j];
}
public static void main(String args[])
{
System.out.println("CS 302 -- " + quarter + " -- Lab " + LabNo);
testProblems(1);
testProblems(2);
}
private static void testProblems(int prob)
{
int noOfLines = prob == 1 ? 100000 : 500000;
System.out.println("-- -- -- -- --");
System.out.println(noOfLines + " test cases for problem " + prob + ".");
boolean passedAll = true;
for (int i = 1; i <= noOfLines; i++)
{
int[][] testCase = null;
boolean passed = false;
boolean exce = false;
try
{
switch (prob)
{
case 1:
testCase = createProblem1(i);
passed = testProblem1(testCase);
break;
case 2:
testCase = createProblem2(i);
passed = testProblem2(testCase);
break;
}
}
catch (Exception ex)
{
passed = false;
exce = true;
}
if (!passed)
{
System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : ""));
passedAll = false;
break;
}
}
if (passedAll)
{
System.out.println("All test passed.");
}
}
private static int[][] createProblem1(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 5;
int[] numbers = getRandomNumbers(size, size);
Arrays.sort(numbers);
int maxK = 0;
for (int i = 0, j = 0; i < size; i = j)
{
for (; j < size && numbers[i] == numbers[j]; j++) { }
maxK = Math.max(maxK, j - i);
}
int k = rng.nextInt(maxK) + 1;
shuffle(numbers);
return new int[][] { numbers, new int[] { k } };
}
private static int[][] createProblem2(int testNo)
{
int size = rng.nextInt(Math.min(1000, testNo)) + 5;
int[] numbers = getRandomNumbers(size, size);
int i = rng.nextInt(size);
int j = rng.nextInt(size - 1);
if (i <= j) j++;
numbers[i] = numbers[j];
return new int[][] { numbers, new int[] { Math.abs(i - j) } };
}
private static void shuffle(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
int rndInd = rng.nextInt(arr.length - i) + i;
int tmp = arr[i];
arr[i] = arr[rndInd];
arr[rndInd] = tmp;
}
}
private static int[] getRandomNumbers(int range, int size)
{
int numbers[] = new int[size];
for (int i = 0; i < size; i++)
{
numbers[i] = rng.nextInt(2 * range) - range;
}
return numbers;
}
}
private static int problem1(int[] arr, int k) {
// Implement me!
Map<Integer, Integer> table = new TreeMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if (table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
} else {
table.put(arr[i], 1);
}
}
for (Map.Entry<Integer,Integer> entry : table.entrySet()) {
//As treemap is sorted, we return the first key with value >=k.
if(entry.getValue()>=k)
return entry.getKey();
}
//Not found
return -1;
}
正如其他人所指出的，有一些错误。首先，初始化 ans,
int ans = 0;
您应该将 ans 初始化为 Integer.MAX_VALUE 以便当您发现一个整数首次出现至少 k 次时 ans 被设置为该整数适当的整数。其次，在您的 for 循环中，没有理由在迭代数组时跳过第一个元素，因此 i 应该初始化为 0 而不是 1。此外，在同一行中，您想要遍历整个数组，并且在您的循环条件下，当 k 不是数组的长度时，您现在有 i < k 。数组的长度由 arr.length 表示，因此条件应该改为 i < arr.length。三、这一行，
if (k < table.get(arr[i])){
在遍历数组时尝试检查一个整数到目前为止是否在数组中至少出现 k 次，< 运算符应更改为 <= 因为这里的关键词是至少k次，而不是“超过k次”。第四，k永远不要改变，这样你就可以摆脱这行代码，
k = table.get(arr[i]);
应用所有这些更改后，您的函数应如下所示：
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
if (k <= table.get(arr[i])) {
ans = Math.min(ans, arr[i]);
}
}else{
table.put(arr[i], 1);
}
}
return ans;
}
伪代码：
- 收集
Map<Integer, Integer>（数字及其计数） 中每个数字的频率
- 将最小值设置为较大的值
- 遍历条目
- 如果条目的值小于
k，则忽略条目
- 如果entry key小于当前的least，存储为least
- 如果条目的值小于
- return最少
一行实现：
private static int problem1(int[] arr, int k) {
return Arrays.stream(arr).boxed()
.collect(groupingBy(identity(), counting()))
.entrySet().stream()
.filter(entry -> entry.getValue() >= k)
.map(Map.Entry::getKey)
.reduce(MAX_VALUE, Math::min);
}
这样就可以过关了！感谢所有帮助过的人！！
private static int problem1(int[] arr, int k)
{
// Implement me!
HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();
int ans = Integer.MAX_VALUE;
for (int i=0; i < arr.length; i++) {
if(table.containsKey(arr[i])) {
table.put(arr[i], table.get(arr[i]) + 1);
}else{
table.put(arr[i], 1);
}
}
Set<Integer> keys = table.keySet();
for(int i : keys){
if(table.get(i) >= k){
ans = Math.min(ans,i);
}
}
if(ans != Integer.MAX_VALUE){
return ans;
}else{
return 0;
}
}