Question

In this programming exercise you will create an algorithm for solving the following version of the m Smallest Numbers problem.   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 [p₁, p₂, …, p_m] has been returned where p_j is the position of the j^th smallest element of L. The original list L has not been changed.

Determine the time complexity and space complexity of your algorithm.

Use Java or Python to implement your algorithm. 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.

You may assume that the elements of the list are unique.

Answer 1

KthSmallestelement.java

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());
   }
  
}
================================================================================
Note: The answer is the indexex if the array and not the values . As per the question.

Thanks, lete me know if there is anything.

Time Complexity is O(MLogN) , Because Min Heap is Used. As we know for a single extraction Heap takes log N time. For M extraction it will take O(MLOGN) Time.