04:54
Question :
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));
Examples
a is
|
then function returns
|
{0, 0, 0, 2, 0, 2, 0, 2, 0, 0}
|
{0, 2, 0, 2, 0, 2, 0}
|
{18}
|
{18}
|
{}
|
{}
|
{-5, -5, -5, -5, -5}
|
{-5}
|
{1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1}
|
{1, 2, 1}
|
{8, 8, 6, 6, -2, -2, -2}
|
{8, 6, -2}
|
public static int[] clusterCompression(int[] a)
{
int[] rtnarray = new int[] { };
if (a.Length != 0)
{
rtnarray = new int[FindCompressedArrayCount(a)];
int currentValue = a[0], j = 0;
rtnarray[j] = currentValue;
for (int i = 1; i < a.Length; i++)
{
if (currentValue != a[i])
{
j++;
currentValue = a[i];
rtnarray[j] = currentValue;
}
}
}
return rtnarray;
}
public static int FindCompressedArrayCount(int[] a)
{
int currentValue = a[0], count = 1;
for (int i = 0; i < a.Length; i++)
{
if (currentValue != a[i])
{
count++;
currentValue = a[i];
}
}
return count;
}
package practice3;
ReplyDeletepublic class ClusterCompression {
public static void main(String[] args) {
int [] result = clusterCompression(new int[] {0, 0, 0, 2, 0, 2, 0, 2, 0, 0});
System.out.println(result);
result = clusterCompression(new int[] {18});
System.out.println(result);
result = clusterCompression(new int[] {});
System.out.println(result);
}
public static int[] clusterCompression(int[] a) {
int[] returnArray = new int[] {};
if(a.length !=0) {
returnArray = new int[FindCompressedArrayCount(a)];
int currentValue = a[0], j=0;
returnArray[j] = currentValue;
for(int i =1; i < a.length; i++) {
if(currentValue !=a[i]) {
j++;
currentValue = a[i];
returnArray[j]= currentValue;
}
}
}
return returnArray;
}
public static int FindCompressedArrayCount(int[] a) {
int currentValue = a[0], count=1;
for(int i =0; i<a.length; i++) {
if(currentValue != a[i]) {
count++;
currentValue = a[i];
}
}
return count;
}
}
output
[I@7852e922
[I@4e25154f
[I@70dea4e