4

I've searched for other threads with a similar problem, but I couldn't find any that apply to me. If I have a variable which has some value, and an array that has a list of values... is it possible for me to efficiently (time efficient, space isn't a constraint) find out the index of the array when the variable matches an element in the array?

I'm getting the variable from reading out of a massive file, and brute force iterating over every possibility will mean several million iterations. I'm willing to do that as a last resort, but I'd rather not. :)

I'm programming in C, if the algorithm depends on that. I don't have an option to program in C++/Python. Thanks!

Edit : The valued that I want to match with the array come in pairs (x,y). If the array matches with x or y, I further process (x,y). But it's vital that the ordering not change if I have to sort it for example.

4

1 に答える 1

2

If space isn't a concern, and you want to know whether a value is contained in the array, you could do something like this:

  • First, create a new array. Let's call the old one v[ ], the new one w[ ], and let i be your iterator through v[ ].

  • Now, make w[v[i]] = 1, and the rest of w[ ] = 0. This basically says "if x is a value in array v[ ], then w[x] = 1". (Note: if you declare w[ ] globally, all of its positions will be initialized with 0, by default)

  • Whenever you want to check for a value contained in v[ ], check w[value] instead. If it equals 1, then the answer is yes.

If you do many checks per array, this should work pretty well. Take note, though, that w[ ] could get pretty big, in size.

Edit: if you want to also keep the index, you could replace the 1's in w[ ] with actual positions - as long as the values do not repeat, this works well.

于 2012-11-29T07:18:08.880 に答える