CODEWITHSUNDEEP
c#javaarraysalgorithm
Luke Vo
Luke Vo

Reputation: 20788

Convert ONE two-dimensional array into TWO one-dimensional arrays

You may feel weird about what I'm asking, but it's true, convert 1 two-dimensional array into 2 one-dimensional arrays.

That was what my teacher asked, and he said he would give a perfect point for whoever answers this (I think, tricky) question. I would happy to convert any 2 or n-dimensional array into one one-dimensional array. But he said 2, so I think there must be something to do with the second array. And, he didn't tell what type of array (int, String or object), so I assume it must be done with any kind of 2-dimensional array.

This is what I will answer him if no one here figure out what he wants: Convert into a 1-dimensional array, and leave the second null (or let it have no element). But I don't think it's a good answer for such a tricky question.

EDIT: Here is my teacher question, word-by-word (he just ask at the end of the session in voice, not in the textbook, as a bonus question(with... a nice bonus reward)): Given a 2-dimensional array, convert it into two 1-dimensional arrays.

I don't know if [][] in Java and C# considered 2-dimensional array, but C# does have [, ], which is 2-dimensional array. We are studying computer algorithm, with no target IDE or language.

EDIT2: I emailed him, and he refused to give additional information (he said it was unfair for others if I have more information than them), and he didn't give any comments about jagged array idea. The only useful thing in his reply: Let [][] be considered 2-dimensional array.

Upvotes: 3

Views: 2017

Answers (4)

Michael J. Barber
Michael J. Barber

Reputation: 25052

Flatten the 2-d array in either row-major or column-major order, storing it in one of the 1-d arrays. Store the shape {n, m} of the array in the other 1-d integer array. Given the indices for an element in the 2-d array of values, you can use the shape to calculate the index in the 1-d array of values.

The two representations are isomorphic, and both allow looking up the values in constant time. It's also similar to how a 2-d array is represented in memory.

Upvotes: 1

Alex
Alex

Reputation: 2146

If I understand your question properly

it's easy m8...

it's only an algorithm question.. not a programming language specific...

you can do it like this:

  1. one array holds the values
  2. second array holds the keys

  3. try to find a workaround in the second array to know what keys you've got..

    For example:
array_1: v0 v1 v2 null v3 v4 v5 null v6 v7 v8 null
array_2: 0  1  2  newR 0  1  2  newR 0  1  2  newR

You can represent it in one array as well... but you need a specific algorithm to figure out when you are located on Y of the matrix.

The problem is that you won't access the data instantly from memory.. this is why there are bi-dimensional arrays

Another way:

  1. keep in array 1 the values

  2. keep in the second array the keys as string like in the following example:

    array1: value1 value2 value3 value4 value5
array2: 0,0    0,1    1,0    1,1    2,0

there are a lot of algorithms but I don't think you will find better than bi-dimensional arrays...

When you look after them you will have less performance.. ofc.. unless you keep them in hashtables.. hashing 0,0 and added as key in a hashtable and add the specified value to that key. then you will look for key "0,0"...

Upvotes: 2

Falanwe
Falanwe

Reputation: 4744

I guess you want to transform you 2-demension array (typed RelevantType[,]) into 2 arrays (typed SomeTypeA[] and SomeTypeB[]) without losing any information?

It's not very difficult: Have the first array be of type RelevantType[], the second one of type int[], copy the content of your 2-dimensionnal array into the first one and its first indices into the second one, and you're done.

Upvotes: 1

JNadal
JNadal

Reputation: 408

I'll bite. It's possible to flatten the entire two-dimensional array into the first of the two one-dimensional arrays by simply reading and writing consistently. I.e. store row 1 then row 2, etc. sequentially in that first array. Whenever you move to the next row, store the index of that next cell (of the first one dimensional array) in the second one-dimensional array, which would essentially become a row index table.

As Jon Skeet said above, this isn't a very well-specified question; perhaps with clarified information, we could better help you.

Upvotes: 6

Related Questions