In Java please Consider an array of n distinct integers, A = [aa, a,-..,a- You c

Question

In Java please

Consider an array of n distinct integers, A = [aa, a,-..,a- You can swap any two elements of the array any number of times. An array is beautiful if the sum of la-al among 0 n is minimal possible (after, possibly, performing some swaps). Given the array A, find and print the minimum number of swaps that should be performed in order to make the array beautiful. Input Format The first line contains a single integer, n, denoting the number of elements in the array A The second line contains n space-separated integers describing the respective distinct values of ao, a,.an- Constraints n105 Output Format Print the minimum number of swaps that should be performed in order to make the array beautiful Sample Input 2 5 3 1 Sample Output Explanation Let's define array B 1,2,3,5] to be the beautiful reordering of array A, as the sum of the absolute values of differences between its adjacent elements is minimal among all permutations and only two swaps (1 with 2 and then 2 with 5) was performed.

Explanation / Answer

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static void reverse(int[] a) {
        int n = a.length;
        for (int i=0; i<n/2; i++) {
            swap(a,i,n-i-1);
        }
    }

    private static int solve(int[] a, int n, int[] sorted) {
        int ans = 0;
        Map<Integer, Integer> value2index = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            value2index.put(a[i], i);
        }

        for (int i = 0; i < n; i++) {
            if (a[i] != sorted[i]) {
                // At index i there must be value sorted[i]

                // Find the position of value sorted[i] in the input array
                int position = value2index.get(sorted[i]);

                // Swap sorted[i] with a[i]
                swap(a, i, position);

                // Update the position of a[position] in the value2index map
                value2index.put(a[position], position);

                // Increment swap count
                ans++;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
      
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int[] sorted = Arrays.copyOf(a, a.length);
        Arrays.sort(sorted);
      
        int ans = solve(Arrays.copyOf(a, a.length), n, sorted);
        reverse(sorted);
        int ansR = solve(a, n, sorted);

        System.out.println(Math.min(ans,ansR));
    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.