In this programming exercise you will create an algorithm for solving the following version of the m Smallest Numbers problem and implement it. Instead of just returning the m smallest values as in homework 1, you want to return a list of the positions where the m smallest values are located without changing the original array. Your algorithm should meet the following specifications: mSmallest( L[1..n], m ) Pre: L is a list of distinct integer values. n is the number of elements in the list. 0 < m ≤ n Post: A list [p1, p2, …, pm] has been returned where pj is the position of the jth smallest element of L. The original list L has not been changed. Your program should: prompt the user to enter the list of numbers prompt the user to enter the value for m print a list of the positions where the m smallest values are located. Determine the time complexity of your algorithm. In addition to your program, add code to count the number of times the characteristic operation of your algorithm is executed by your program. Compare that number to your determined time complexity. You may assume that the elements entered by the user are unique. So, what you will be turning in is your algorithm and your complexity analysis.
Use Python to implement your
In this
Your algorithm should meet the following specifications:
mSmallest( L[1..n], m )
Pre: L is a list of distinct integer values. n is the number of elements in the list. 0 < m ≤ n
Post: A list [p1, p2, …, pm] has been returned where pj is the position of the jth smallest element of L. The original list L has not been changed.
Your program should:
- prompt the user to enter the list of numbers
- prompt the user to enter the value for m
- print a list of the positions where the m smallest values are located.
- Determine the time complexity of your algorithm.
- In addition to your program, add code to count the number of times the characteristic operation of your algorithm is executed by your program. Compare that number to your determined time complexity.
You may assume that the elements entered by the user are unique.
So, what you will be turning in is your algorithm and your complexity analysis.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class KthSmallestelement {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
HashMap<Integer, Integer> map= new HashMap<Integer, Integer>();
List<Integer> list = new ArrayList<Integer>();
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of elements");
int n= sc.nextInt();
int values[] = new int[n];
System.out.println("Enter Elements");
for(int i=0;i<n;++i){
values[i] = sc.nextInt();
pq.offer(values[i]);
map.put(values[i], i);
}
System.out.println("Enter the number of smallest values");
int m= sc.nextInt();
for(int i=1;i<=m && i<=n;++i){
//System.out.println();
list.add(map.get(pq.poll()));
}
System.out.println(list.toString());
}
}
Step by step
Solved in 2 steps with 1 images
