0

I am doing a program in C which needs to take in a set of values (integers) into a 2D array, and then performs certain mathematical operations on it. I have decided to implement a check in the program as the user is inputting the values to avoid them from entering values that are already present in the array.

I am however unsure of how to go about this check. I figured out I might need some sort of recursive function to check all the elements previous to the one that's being entered, but I don't know how to implement it.

Please find below a snippet of my code for illustrative purposes:

Row and col are values inputted by the user for the dimension of the array

for (int i=0; i<row;i++){
    for (int j=0; j<col; j++){
        scanf("%d", &arr[i][j]); //take in elements
    }
}
for (int i = 0; i < row; i++)
    {
        for (int j = 0; i < col; j++)
        {
            if (arr[i][j] == arr[i][j-1]){
                printf("Duplicate.\n");}
            else {}
            }

    }

I know this is probably not correct but it's my attempt. Any help would be much appreciated.

Lorenzo Battilocchi
  • 862
  • 1
  • 10
  • 26
  • 1
    Can the values in either or both dimensions be sorted? – BurnsBA Apr 25 '17 at 13:57
  • I've no problem doing it for 1D array, but it's the fact that it's a 2D array that really confuses me... @BurnsBA – Lorenzo Battilocchi Apr 25 '17 at 13:58
  • 2
    You are aware that `=` is not comparison operator, right? – user694733 Apr 25 '17 at 13:59
  • 2
    If you can do it for a 1D array, then you can do it for a 2D array, which is just an array of 1D arrays. Simply apply your 1D array technique to all of the element arrays that have been partially or wholly filled. – John Bollinger Apr 25 '17 at 13:59
  • @user694733 will correct that now, type-oh! – Lorenzo Battilocchi Apr 25 '17 at 13:59
  • This depends on the nature of the data. If the data can be stored in any order, it can be kept sorted, meaning you can binary search through it efficiently when looking for duplicates. If the data is stored in the order it is entered, then it is a kind of FIFO, in which case a 2D array is not necessarily the best choice. Don't mix up the mathematical concept _matrix_ with the binary representation concept arrays. With programming, you can represent a mathematical matrix in many ways. It might be more suitable for you to use some form of look-up table or a linked list, rather than an array. – Lundin Apr 25 '17 at 14:03
  • As in, there isn't enough information about the nature of the data to answer the question. – Lundin Apr 25 '17 at 14:03

2 Answers2

1

I would suggest that your store every element you read in a temporary 1D array. Everytime you scan a new element, traverse the 1D array checking if the value exists or not. Although this is not optimal, this will be at least less expensive than traversing the 2D array everytime.

Example:

int temp[SIZE];
int k,elements = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        scanf("%d",  &arr[i][j]); //take in elements
        temp[elements] = arr[i][j];
        elements++;
        for (int k = 0; k < elements; k++) {
            if (temp[k] == arr[i][j])
                printf("Duplicate.\n"); //or do whatever you wish
        }
    }
}
Mohammed Bakr Sikal
  • 357
  • 2
  • 7
  • In C, 2D arrays are implemented the same as 1D, so the difference is negligible. – ivan_pozdeev Apr 25 '17 at 14:15
  • @ivan_pozdeev Well, no, they are implemented as 1D arrays of 1D arrays. The layout is of course the elements of the second row just following the elements of the first row without additional padding, that much is guaranteed by the standard. However, that does not allow type punning a 2D array to an `int*` and accessing the data as a 1D array (as in `for(int i = 0; i < row*col; i++) { if(currentVal == arr[0][i]) printf("Duplicate.\n"); }`), afaik, strict aliasing rules seem to prohibit this – cmaster - reinstate monica Apr 25 '17 at 14:56
  • @cmaster [do they?](http://stackoverflow.com/questions/2151084/map-a-2d-array-onto-a-1d-array-c/33406032#33406032) – ivan_pozdeev Apr 25 '17 at 15:04
  • 1
    @ivan_pozdeev Well, the memory layout is exactly as the answer you linked puts it, so much is true. The problem is, when that answer performs this cast `int* arr2 = (int*)arr;` and subsequently accesses the entire `arr` via this pointer, it invokes undefined behavior due to a strict aliasing violation, if I am not much mistaken. The code is legal, it will compile, and will likely even give the expected result, but there is no guarantee on what will actually happen. Afaik, the compiler is free to assume that `arr[1][0]` won't ever be accessed via `arr2`. – cmaster - reinstate monica Apr 25 '17 at 15:30
1

A balanced tree inserts and searches in O(log N) time.

Since the algorithms are quite simple & standard and were published in the seminal books by Knuth, there are plenty of implementations out there, including a clear and concise one at codereview.SE (which is thus automatically CC-BY-SA 3.0; do apply a bugfix in the answer). Using it (as well as virtually any other one) is simple: start with node* root = NULL;, then insert and search, and finally free_tree.

Asymptotically, the best method is a hash table with O(1) for both, but that is probably an overkill (the algorithms are much more complex and memory footprint is larger) unless you have a lot of numbers. For C++, there's a standard implementation, yet there are plenty 3rd-party ones for C, too.

If your number of input values is small, even the tree may be an overkill, and simply looking through previous values would be fast enough. If your 2D array is contiguous in memory, you can access it as 1D with int* arr1d = (int*)&arr2d.

Community
  • 1
  • 1
ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152