找到所需的最小交换数，以使所有0和所有1在一起 [英] Find the minimum number of swaps required such that all the 0s and all the 1s are together

问题描述

我需要找到所需的最小交换数，以使所有0和所有1在一起.

I need to find the minimum number of swaps required such that all the 0s and all the 1s are together.

这是我的代码:

class GFG {

    static int minSwaps(int arr[], int n) {
        int noOfOnes = 0;
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 1)
            noOfOnes++;
        }
        int x = noOfOnes;
        int maxOnes = Integer.MIN_VALUE;
        int preCompute[] = new int[n];
        if (arr[0] == 1)
            preCompute[0] = 1;
        for (int i = 2; i < n; i++) {
            if (arr[i] == 1) {
                preCompute[i] = preCompute[i - 1] + 1;
            } else {
                preCompute[i] = preCompute[i - 1];
            }
        } 

        for (int i = x - 1; i < n; i++) {
            if (i == (x - 1)) {
                noOfOnes = preCompute[i];
            } else {
                noOfOnes = preCompute[i] - preCompute[i - x];
            }
            if (maxOnes < noOfOnes)
                maxOnes = noOfOnes;
        }

        int noOfZeroes = x - maxOnes;
        return noOfZeroes;
    }

    public static void main (String[] args) { 
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        for (int test = 1; test <= t; test++) {
            int n = s.nextInt();
            int[] a = new int[n];
            for (int j = 1; j <= n; j++) {
                a[j] = s.nextInt();
            }
            System.out.println(minSwaps(a, n));
            System.out.println("\n");
        }
    }
}

我收到了 ArrayIndexOutOfBoundsException :

error : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
    at GFG.main(solution.java:56)

推荐答案

您似乎正在尝试冒泡.因此，我从Wikipedia复制了 bubblesort伪代码实现，并用一个计数器进行了增强:

It looks like you're trying to do bubblesort. So I copied this bubblesort pseudocode implementation off of Wikipedia and augmented it with a counter:

bubbleSort(Array A)
  swap_counter = 0          // start at 0
  for (n=A.size; n>1; --n){
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        swap_counter++      // count a swap
      }
    }
  }
  return swap_counter       // return the result

这篇关于找到所需的最小交换数，以使所有0和所有1在一起的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！