Ta bort duplicerade element i en array
Jag försöker skapa en metod som hittar de gemensamma elementen i två arrayer, lägger in dessa i en egen array och tar sedan bort de som är duplicerade. Ett exempel på input kan vara
int [] arr1 = {1,2,3}
int [] arr2 = {1,7,0,7,8,9,1,1,1}output bör då vara {1}
Med koden som jag har nu så skulle jag få ut {1,0,0,0,0,0,1,1,1}
int[] inBoth(int[] arr1, int[] arr2) {
int count = 0;
for (int i = 0; i < arr1.length; i++) {
for (int k = 0; k < arr2.length; k++) {
if (arr1[i] == arr2[k]) {
count++;
}
}
}
int[] commons = new int[count];
for (int i = 0; i < arr1.length; i++) {
for (int k = 0; k < arr2.length; k++) {
if (arr1[i] == arr2[k]) {
commons[i] = arr1[i];
}
}
}
return commons;
}
}
Så med andra ord, metoden ska hitta element som finns i både arr1 och arr2?
Ser inte hur du skulle få {1,0,0,0,0,0,1,1,1} med denna kod.
Du kommer få {1, 0, 0, 0}
beerger skrev:Så med andra ord, metoden ska hitta element som finns i både arr1 och arr2?
Ja
Det här är ett exempel av det jag får:
Du skulle kunna köra merge sort och i en ny array lägga alla unika element. Hur vet vi at Ett element är unikt? Det ser vi lätt genom att jämföra nuvarande element med nästa.
Då får vi en komplexitet på nlogn vilket inte allt för dåligt.
Jag förstod mig inte riktigt på merge and sort, men jag testade denna approach istället
int[] inBoth(int[] arr1, int[] arr2) {
int count = 0;
for (int i = 0; i < arr1.length; i++) {
for (int k = 0; k < arr2.length; k++) {
if (arr1[i] == arr2[k]) {
count++;
}
}
}
int[] commons = new int[count];
for (int i = 0; i < arr1.length; i++) {
for (int k = 0; k < arr2.length; k++) {
if (arr1[i] == arr2[k]) {
commons[i] = arr1[i];
}
}
}
int [] arrayReturn = removeduplicates(commons, commons.length);
return arrayReturn;
}
public static int [] removeduplicates(int a[], int n)
{
if (n == 0 || n == 1) {
return a;
}
// creating another array for only storing
// the unique elements
int[] temp = new int[n];
int j = 0;
for (int i = 0; i < n - 1; i++) {
if (a[i] != a[i + 1]) {
temp[j++] = a[i];
}
}
temp[j++] = a[n - 1];
// Changing the original array
for (int i = 0; i < j; i++) {
a[i] = temp[i];
}
return temp;
}Den tar bort de duplicerade talen fast ersätter de med nollor så att det blir så här nu:
[0, 2, 3, 6, 0, 0, 0, 0, 0, 0, 0, 0]
Jag vill att den enbart ska returnera [2,3,6]
Om du inte bryr dig om tidskomplexitet så kan du göra följande.
Gör en array av storleken n+m, dvs en array stor nog att ta emot alla dina element. Använd den inbyggda sort funktionen, lägg alla unika element i en ny array.
Notera att det finns mycket effektivare lösningar men jag antar att om du inte begriper merge sort så har du förmodligen inte börjat prata om algoritmer. Då känns det orimligt att din lärare skulle bry sig om tidskomplexitet.
