Nombre minimal d’échanges requis pour minimiser la somme des différences absolues entre les éléments de tableau adjacents

<script>

        

        

        

        function mycmp(a, b) {

            return a[0] > b[0];

        }

        

        

        

        function minSwapsAsc(arr, n) {

            

            

            let arrPos = new Array(n);

            for (let i = 0; i < n; i++)

                arrPos[i] = new Array(2);

            for (let i = 0; i < n; i++) {

                arrPos[i][0] = arr[i];

                arrPos[i][1] = i;

            }

            

            

            arrPos.sort(function (a, b) { return a[0] - b[0] })

            

            

            let vis = new Array(n);

            for (let i = 0; i < n; i++)

                vis[i] = false

            

            let ans = 0;

            

            for (let i = 0; i < n; i++) {

                

                

                if (vis[i] || arrPos[i][1] == i)

                    continue;

                

                

                let cycle_size = 0;

                

                let j = i;

                while (!vis[j]) {

                    vis[j] = 1;

                    

                    j = arrPos[j][1];

                    

                    cycle_size++;

                }

                

                

                if (cycle_size > 0) {

                    ans += (cycle_size - 1);

                }

            }

            return ans;

        }

        

        

        

        function minSwapsDes(arr, n) {

            

            

            let arrPos = new Array(n);

            for (let i = 0; i < n; i++)

                arrPos[i] = new Array(2);

            for (let i = 0; i < n; i++) {

                arrPos[i][0] = arr[i];

                arrPos[i][1] = i;

            }

            

            

            arrPos.sort(function (a, b) { return b[0] - a[0] })

            

            let vis = new Array(n);

            for (let i = 0; i < n; i++)

                vis[i] = false

            

            

            let ans = 0;

            

            for (let i = 0; i < n; i++) {

                

                

                

                if (vis[i] || arrPos[i][1] == i)

                    continue;

                

                

                let cycle_size = 0;

                

                let j = i;

                while (!vis[j]) {

                    vis[j] = 1;

                    

                    j = arrPos[j][1];

                    

                    cycle_size++;

                }

                

                

                if (cycle_size > 0) {

                    ans += (cycle_size - 1);

                }

            }

            return ans;

        }

        

        

        

        

        function minimumSwaps(arr) {

            

            let S1 = minSwapsAsc(arr, arr.length);

            

            let S2 = minSwapsDes(arr, arr.length);

            

            return Math.min(S1, S2);

        }

        

        let arr = [ 3, 4, 2, 5, 1 ];

        document.write(minimumSwaps(arr));

        

    </script>

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut