你说得很有道理

不过你的假设就完全没有初始条件了，而原题一开始还是有规律的。

另外assign value是不行的。事实上数组里每个元素应该是一个结构，包括一个整数key和一个value。这里只不过简化成只有key而已。

我把你的问题变成这样一个程序问题，你看看合适不合适：
------------------------------------------------
有个长度为n的数组a[n]，初始随机存储0,1,...n-1。要求最终a[f(k)]=k，其中f(k)是从0,1,...,n-1的一个一一对应的函数，计算f(k)需要常数时间。
------------------------------------------------
下面是程序，这里f(n)可以自己另外定义。根本算法和我前面说的没有任何区别。

using System;
using System.Collections.Generic;
using System.Text;

namespace netiq
{
class Program
{
static int numOperations = 0;
const int n = 10;

static int[] GenRandData(int n)
{
Random rand = new Random(0);
int[] data = new int[n];
for (int i = 0; i < n; i++) { data[i] = i; }
for (int i = 0; i < n - 1; i++)
{
int k = rand.Next(n - i);
int j = data[i]; data[i] = data[k]; data[k] = j;
}
return data;
}

static int f(int k)
{
return (k % 2 > 0) ? ((k - 1) / 2 + n / 2) : k / 2;
}

static string toString(int[] data)
{
string str = data[0].ToString();
for (int i = 1; i < data.Length; i++)
{
str += " " + data[i];
}
return str;
}

static void ReOrder(int[] data)
{
for(int k = 0; k < data.Length; k++)
{
if (k == data[f(k)]) continue;

int start = data[f(k)];
while(start != k)
{
int temp = data[f(start)];
data[f(start)] = start;
start = temp;
numOperations++;
}
data[f(k)] = k;
}
}


static void Main(string[] args)
{
int[] obj = new int[n];
for (int i = 0; i < n; i++) { obj[f(i)] = i; }
Console.WriteLine(toString(obj));

int[] data = GenRandData(n);
Console.WriteLine(toString(data));
ReOrder(data);
Console.WriteLine(toString(data));
Console.WriteLine(numOperations);
return;
}
}
}

所有跟帖： 

• 我还是觉得我们在说两件不同的事 -康MM- ♀ (0 bytes) () 08/06/2009 postreply 17:49:24