美国面试题

欢迎关注 ： huamaodashu.com

Define a cluster in an integer array to be a maximum sequence of elements that are all the same value. For example, in the array {3, 3, 3, 4, 4, 3, 2, 2, 2, 2, 4} there are 5 clusters, {3, 3, 3}, {4, 4}, {3}, {2, 2, 2, 2} and {4}. A cluster-compression of an array replaces each cluster with the number that is repeated in the cluster. So, the cluster compression of the previous array would be {3, 4, 3, 2, 4}. The first cluster {3, 3, 3} is replaced by a single 3, and so on.

Write a function named clusterCompression with the following signature If you are programming in Java or C#, the function signature is
int[ ] clusterCompression(int[ ] a)
If you are programming in C++ or C, the function signature is
int *clusterCompression(int a[ ], int len) where len is the length of the array.
The function returns the cluster compression of the array a. The length of the returned array must be equal to the number of clusters in the original array! This means that someplace in your answer you must dynamically allocate the returned array.
In Java or C# you can use
int[ ] result = new int[numClusters];
In C or C++ you can use
int *result = (int *)calloc(numClusters, sizeof(int));

测试样例：

java代码实现：

public class clusterCompression {
    public static void main(String[] args) {

//        int [] a= {0, 0, 0, 2, 0, 2, 0, 2, 0, 0};
//        int [] a= {18};
//        int [] a= {};
//        int [] a= {-5, -5, -5, -5, -5};
//        int [] a= {1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1};
        int [] a= {8, 8, 6, 6, -2, -2, -2};



        System.out.println(clusterCompression(a).length);

    }

    public static int[] clusterCompression(int[] a){



        if(a.length==0){
            return a;
        }

        ArrayList<Integer> array = new ArrayList<>();

        int tmp =a[0];
        array.add(tmp);
        for (int i = 1; i < a.length; i++) {
            if(tmp == a[i]){
                continue;
            }else {
                array.add(a[i]);
                tmp = a[i];
            }

        }

        int [] result = new int[array.size()];
        int i =0;
        for(Integer arr: array){
            result[i]=arr;
            System.out.println(arr);
            i++;


        }

        return result;
    }
}