I'm still a newbie when it comes to programming in C so please be thorough in explanations. Also, this is a homework assignment so I would love it if you could help me solve this problem. I've looked around the site and could only find posts similar to this question. The ones that I did find mentioned things like hash tables, which I did not learn so I doubt those kinds of things can be used.
For my assignment, I have two unsorted integer arrays of the same length. They can only have integers in the range of 0-99. Duplicate elements are allowed. The goal is to see whether they have the same elements, therefore checking if they are equal, without sorting them. My professor also said that it has to run in linear time, so sorting them would not be an option.
For example,
A[4]={1,2,3,4}
B[4]={4,3,2,1}
These arrays would be equal. However,
A[3]={1,1,2}
B[3]={2,2,1}
These arrays are not equal.
The algorithm that I came up with goes like this:
The first for loop iterates through the first array and the inner for loop iterates through the second array. It would check to see if the current element in the first array is equal to an element in the second. If they are equal, then the outer loop iterates and the inner for loop starts at the first element again, checking to see if the current element in the first array ever matches with an element in the second. If not, then it exits out of both loops and returns 0 indicating that they are not equal. This algorithm does not run in linear time. Also, it does not check for duplicates since the inner for loop checks all the elements in the second array each time.
I was thinking of changing the value of the element in the second array to something extremely large every time it was found to be equal to an element in the first array. I think that way it would get rid of the duplicate problem. But I still need help making a faster algorithm and understanding my error. Thanks.