Compare each array element with each without nested loop
Each element of the array must be compared with each. How can I get rid of the nested loop in my case, because it greatly increases the execution time?
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(towns[i] - towns[j] == d)
count++;
}
}
4 answers
If all boils down to count++; and the array of numbers is integer and with a small range, then we do something like this:
- Cycle by i. Building a histogram of our array (i.e., calculating which values are how many).
- Cycle by j. towns[i] - towns[j] == d this implies towns[i] == towns[j] + d. At the first stage, we have already calculated the number of towns[i]. That is, if towns[j]=10; d=2, then towns[i] should be 12 - we look at the 12th element in the histogram array and add it to the total. Moving on to the next j
Complexity of the order O(n)
If you need to output pairs or very large numbers, then at the first stage you do not need to build a histogram, but (apparently) write "value, index" in the dictionary (only the dictionary should be able to write several lines with the same value). And the complexity will be the same order of O (n).
Does not require sorting the array.
I will add: in the simple case, you can still speed up. For this, in the second step, we do not use a large array. All the information is in the array of histograms. Cycle by i: count+=histogram[i]*histogram[i+d]
Sort it. Write down partial differences. Go from the first until the sum of the partial differences exceeds d. Then subtract the first partial difference and start working further with the stored difference.
Something like for the set 7 5 9 12 4 8 11 looking for 3
4 5 7 8 9 11 12
разности: 1 2 1 1 2 1
Этап 1 : 1 3 4- все, найдено, выводим. Далее - 4. Стоп, вычли 1, перешли к
Этап 2 : 2 3 4- нашли, выводим. Далее - опять 4. Стоп, вычли 2, перешли к
Этап 3 : 1 2 4 - Нашли, выводим. Вычитание, переход к
Этап 4 : 1 3 4 - Нашли, выводим. Вычитание, переход к
Этап 5 : 2 3 - Нашли, выводим. Вычитание, переход к
Этап 6 : 1 - более сравнивать нечего.
So, found 4-7, 5-8, 8-11, 9-12
"In my opinion, so " (c) Pooh
You can do this by using a movable window. In total, there are two passes of the array, but sorting is needed.
int[] towns = new int[]{4 , 5 , 7 , 8 , 9 , 11 , 12};
Arrays.sort(towns);
int count = 0;
int d = 3;
int i = towns.length-1;
int j = towns.length-2;
while(!(j==0 && towns[i]-towns[j] < d)){
if(towns[i]-towns[j] == d) count++;
if(towns[i]-towns[j] < d) j--;
else i--;
}
Sorry for the carelessness in the composition of the question:)
The essence of the problem was to find the number of pairs of array elements whose difference is equal to d.
It all came down to replacing the nested loop with something like this:
int j = 0;
int count = 0;
for(int i = 0; i < n; i++) {
while(a[i] - a[j] > d)
j++;
if(a[i] - a[j] == d)
count++;
}