Question

Write an algorithm (pseudo-code) that takes an unsorted list of n integers and outputs a sorted list of all duplicate integers. There must be no duplicates in the output list, also the output list should be a sorted list. The algorithm must run in O(n) time. Show your analysis of the running time. Note: Assume that inputs are integer values from 0 to 255. (Hint: use the concept that being used in the separate chaining)

Answer 1

Answer:

brainliest if it did help you

Explanation:

Given array : A[0...n-1]Now, create a count array Cnt[0...n-1]then, initialize Cnt to zero

for(i=0...n-1)

Cnt[i]=0 ---------O(n) time

Linearly traverse the list and increment the count of respected number in count array.

for(i=0...n-1)

Cnt[A[i]]++; ---------O(n) time

Check in the count array if duplicates exist.

for(i=0...n-1){

if(C[i]>1)

output (i); -----------O(n) time

}

analysis of the above algorithm:

Algorithm takes = O(1 + n + n + n)

                           = O(n)          

//java code

public class SortIntegers {

  public static void sort(int[] arr) {

    int min = arr[0];

    int max = arr[0];

    for (int i = 0; i < arr.length; ++i) {

      if (arr[i] > max) {

        max = arr[i];

      }

      if (arr[i] < min) {

        min = arr[i];

      }

    }

    int counts[] = new int[max - min + 1];

    for (int i = 0; i < arr.length; ++i) {

      counts[arr[i] - min]++;

    }

    for (int i = 0; i < counts.length; ++i) {

      if (counts[i] > 1) {

        System.out.print((i + min) + " ");

      }

    }

    

    System.out.println();

  }

  public static void main(String[] args) {

    sort(new int[] { 5, 4, 10, 2, 4, 10, 5, 3, 1 });

  }

}