c - abs() 在此 C 代码中的用途是什么

Question

我有一段代码可以找出大小为 n 的数组中的重复元素。其中元素满足 1 <= arr[i] <= n ，代码如下:

#include<stdio.h>
#include<stdlib.h>

void printTwoElements(int arr[], int size)
{
    int i;
    printf("\n The repeating element is");

    for(i = 0; i < size; i++)
    {
        if(arr[abs(arr[i])-1] > 0)
        {
            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
        }
        else
        {
            printf(" %d ", abs(arr[i]));
        }
    }
}

/* Driver program to test above function */
int main()
{
    int arr[] = {7, 3, 4, 5, 5, 6, 2};
    int  n = sizeof(arr)/sizeof(arr[0]);
    printTwoElements(arr, n);
    return 0;
}

我想知道abs()的用途在这个给定的代码中？

Answer 1

在算法过程中，一些数组条目被设置为负值作为标记。因此，当条目用作数组的索引时，必须取条目的绝对值。

希望不要破坏任何东西:

该算法要求 n 元素数组的数组条目都在 1 和 n 之间(含 1 和 n)。如果任何条目大于n或小于-n或0，它将访问无效地址，如果任何元素为负，则标记逻辑将失败。

算法的逻辑是:

for each array element e:
    if the value at (e-1) is positive, e has not yet been seen,
                   negate the value at (e-1) to mark e as seen
    otherwise, e has already been seen, so print it

因此，由于数组项在运行算法的过程中变为负数，因此必须取绝对值以获得有效索引。

让我们按照修改示例的算法来看看它是如何工作的:

before: arr = { 7, 3, 4, 5, 5, 3, 2}
i == 0: arr[0] = 7
        arr[7-1] is 2 > 0 ~> negate
        arr = { 7, 3, 4, 5, 5, 3, -2}
i == 1: arr[1] = 3
        arr[3-1] is 4 > 0 ~> negate
        arr = { 7, 3, -4, 5, 5, 3, -2}
i == 2: arr[2] is -4 ~> abs for indexing
        arr[4-1] is 5 > 0 ~> negate
        arr = { 7, 3, -4,-5, 5, 3, -2}
i == 3: arr[3] is -5 ~> abs for indexing
        arr[5-1] is 5 > 0 ~> negate
        arr = { 7, 3, -4, -5, -5, 3, -2}
i == 4: arr[4] is -5 ~> abs for indexing
        arr[5-1] is -5 < 0 ~> print abs(-5) as duplicate
i == 5: arr[5] is 3
        arr[3-1] is -4 < 0 ~> print abs(3) as duplicate
i == 6: arr[6] is -2 ~> abs for indexing
        arr[2-1] is 3 > 0 ~> negate
        arr = { 7, -3, -4, -5, -5, 3, -2}

        indices of positive entries: 0, 5 ~> 1 and 6 not in original array
        indices of negative entries: 1, 2, 3, 4, 6 ~> 2, 3, 4, 5, 7 in original array