一道关于数组的题

zero · #1 (**permalink**) 2006-03-04

有一个数组A[1..N]，里面任一项满足: 1 <= A[i] <= N，现求一算法，判断A[1..N]中的项是否有重复。可以修改原来A[1..N]中的项。

注意: 把A[1..N]中的所有项加起来这种办法是行不通的。

bankrock · #2 (**permalink**) 2006-03-04

这个简单啊，计数就可以了.

代码:

void Repeat(vector<int> const& A)
{
	vector<int> count(A.size(), 0);

	for (int i = 0; i < A.size(); ++i)
		++count[A[i] - 1];

	for (int i = 0; i < A.size(); ++i)
		if (count[i] > 1)
			cout << (i + 1) << " ";
	cout << endl;
}

PS.可以给代码加亮的Highlight标签在那里？

polyrandom · #3 (**permalink**) 2006-03-04

1.我觉得这道题目空间复杂度可以做到O(1)的
2.那个加亮的是highlight，highlight="C++"/highlight="java"之类的

zero · #4 (**permalink**) 2006-03-04

呵呵，的确，空间复杂度可以O(1)，而且不是用bit这种，注意条件，A[1..N]可以修改。

cat · #5 (**permalink**) 2006-03-04

把A[i]和A[A[i]]交换如何?

C++ 代码:

bool f(int *a, int n)
{
  for (int i = 0; i < n; ++i)
  {
    while (a&#91;i] != i)
    {
      if (a&#91;a[i]] == a[i]) return false;
      int t = a&#91;i];
      a&#91;i] = a[a[i]];
      a&#91;a[i]] = t;
    }
  }
  return true;
}

PS: 这段代码是错的，谁高兴挑一下，用肉眼比较娱乐呵呵

bankrock · #6 (**permalink**) 2006-03-04

NB的办法啊！
改改看：

C++ 代码:

bool f(int *a, int n)
{  
      for (int i = 0; i < n; ++i)  
      {    
           while (a&#91;i] != i + 1)    
           {      
               if (a&#91;a[i] - 1] == a[i]) return false;      
               int t = a&#91;i];      
               a&#91;i] = a[a[i] - 1];      
               a&#91;a[i] - 1] = t;    
           } 
      }  
      return true;
}

bankrock · #7 (**permalink**) 2006-03-05

能力有限，肉眼果然还是不行啊，没看出关键问题所在

C++ 代码:

bool f(int *a, int n)
{        
    for (int i = 0; i < n; ++i)        
    {               
        while (a&#91;i] != i + 1)               
        {                     
            if (a&#91;a[i] - 1] == a[i]) return false                             
            int t = a&#91;i];
            a&#91;i] = a[t - 1];   //注意index的一致                 
            a&#91;t - 1] = t;       //注意index的一致    
                          }
    }        
    return true;
}

cat · #8 (**permalink**) 2006-03-05

呵呵我也是调试出来的

zero · #9 (**permalink**) 2006-03-05

cat是正解哈

Meta · #10 (**permalink**) 2006-03-05

谁给出复杂度分析和正确性证明吧.

zero · #11 (**permalink**) 2006-03-05

正确性的话，比较明显，就算了吧.

复杂度分析个最坏情况吧。遍历的话，整个数组一遍，然后交换最多发生n-1次吧，比如
2341 => 3241 => 4231 = > 1234，或者是4123 => 3124 => 2134 => 1234。好像不太可能有其他情况会有n-1次了。也就是这个permutation只有一个cycle，长度为n。咔咔，学过抽象代数的，可以讲一下。

Meta · #12 (**permalink**) 2006-03-05

恩.
这种做法有点类似在特殊元素情况下的交换排序的一趟趟的做法. 如果每次都能成功交换的话, 其实就等于每次让一个元素归位; 最多n-1次交换后, 应当就是一个有序的数组了. 而且如果能够n-1交换的话, 该数组必然没有重复的元素, 接下来的每个位置就没有必要去检测了. 就如zero举的4个元素的例子, 在处理完第一个位置的元素时, 总共交换了3次(n = 4), 此时数组已经变成有序的了, 接下来就不可能再发生交换了, 可以直接结束循环退出.

tomato · #13 (**permalink**) 2006-03-05

引用:

作者: bankrock

NB的办法啊！
改改看：
[highlight="C++"]
bool f(int *a, int n)
{
for (int i = 0; i < n; ++i)
{
while (a[i] !=...

其实你仔细想想
这个方法和你的计数的方法是一样的
你的计数的方法用了一个数组
完全可以省去多用的空间
只要你按照同样的方式用原来数组的空间来计数
当然细节方面要做点修改
在原代码return false的地方改为计数
而且计数的1用N+1开始，保证不会与原来数组的1～N重复

tomato · #14 (**permalink**) 2006-03-05

引用:

作者: Meta

谁给出复杂度分析和正确性证明吧.

复杂度，最多交换N次，因为每交换1次就放好了1个
由于遍历了一遍数组，还有N次操作
所以复杂度为O(N)

正确性证明
1、若没有重复
a[a[i]] == a[i]永远不会成立，所以程序可以返回true
2、若有重复
不妨设a[p] = a[q] = k，由于每个元素至少访问一次（由外层的for可以保证），不妨设先访问访问a[p]，要么返回false要么设a[k] = k，那么访问a[q]的时候一定会满足a[a[q]] == a[q]的条件，使得返回false
3、最后证明一下不可能死循环，实际上由复杂度为O(N)的证明就可以得出

cat · #15 (**permalink**) 2006-03-05

引用:

作者: tomato

其实你仔细想想
这个方法和你的计数的方法是一样的
你的计数的方法用了一个数组
完全可以省去多用的空间
只要你按照同样的方式用原来数组的空间来计数

对的，我就是看到zero说可以修改数组，pora说O(1)，然后就觉得bankrock那个数组似乎多余了。

bankrock · #16 (**permalink**) 2006-03-06

引用:

作者: tomato

其实你仔细想想
这个方法和你的计数的方法是一样的
你的计数的方法用了一个数组
完全可以省去多用的空间
只要你按照同样的方式用原来数组的空间来计数
当然细节方面要做点修改
在原代码return false的地方改为计数
而且计数的1用N+1开始，保证不会与原来数组的1～N重复

没看懂，这个计数放在那里呢？修改原数组的数据会导致接下来的比较出错吧。

tomato · #17 (**permalink**) 2006-03-06

可修改原数组的计数
时间O(n)、空间O(1)

c++ 代码:

#include <vector>
#include <algorithm>
using namespace std;
 
template <class T>
void count(vector<T>& array)
{
    int size = static_cast<int>(array.size());
    for(int i = 0; i < size; ++i)
    {
        while( (array&#91;i] < size)
              && (array&#91;array[i]] < size) 
              && (array&#91;i] != array[array[i]]) )
        {
            swap(array&#91;i], array[array[i]]);
        }
        if(array&#91;i] >= size) {
            continue;
        }
        else if(array&#91;array[i]] >= size) {
            ++array&#91;array[i]];
            array&#91;i] = size;
        }
        else if(array&#91;i] == i) {
            array&#91;i] = size + 1;
        }
        else if(array&#91;i] == array[array[i]])    {
            array&#91;array[i]] = size + 2;
            array&#91;i] = size;
        }
    }
    for(int i = 0; i < size; ++i)
    {
        array&#91;i] -= size;
    }
}

bankrock · #18 (**permalink**) 2006-03-06

琢磨了好久，终于有点开窍了。这个不停swap的步骤就是为了腾出计数的空间，比如A[4] = { 1, 3, 0, 2 }，我们希望在计数结束时A[i] = (i的个数)的话，如果直接A[A[0]] = 1可以记录下A[0]（也就是1）的个数增加了1，但是3就被抹杀了，而A[A[i]] = A[i]的情况可以既记数又不至于覆盖原来的数据。

johnson · #19 (**permalink**) 2006-03-14

等差数列的和公式是：（首项 +　末项）　*　项数　／　２
１到Ｎ的和则为Ｎ＊（Ｎ　＋ 1） / 2
下面证明Ｎ＊（Ｎ　＋ 1） / 2这个值在N个数中，只能是N个互不相同的数的和，1<=每一个数<=N
这个证明省略，用数学归纳法一下就能出来。

证明了上面，也就说明，1、2、3……N之和必为Ｎ＊（Ｎ　＋ 1） / 2，而Ｎ＊（Ｎ　＋ 1） / 2必为1、2、3……N之和。

根据题目已知条件，1 <= a[i] <= N
将数组求和，与Ｎ＊（Ｎ　＋ 1） / 2比较，不等则说明有重复。（这里又是个证明，妈d，没办法，力求严谨，如果不等又不重复，说明，a[i]只能是从1到N，而从1到N的和只能是Ｎ＊（Ｎ　＋ 1） / 2，矛盾。所以，如果和不等于Ｎ＊（Ｎ　＋ 1） / 2，说明必定有数字重复）

空间复杂度O（1），时间复杂度O（N）-〉求和

#include <vector>
using namespace std;

static const unsigned int N = 100;
bool IsNumberDuplicate(const vector<int>& array) {
int i = 0;
int sum = 0;
while (i++ < N) {
sum += array[i];
}

if (sum != (1 + N) * N / 2) {
return true;
}

return false;

}

zero · #20 (**permalink**) 2006-03-14

引用:

作者: johnson

等差数列的和公式是：（首项 +　末项）　*　项数　／　２
１到Ｎ的和则为Ｎ＊（Ｎ　＋ 1） / 2
下面证明Ｎ＊（Ｎ　＋ 1） / 2这个值在N个数中，只能是N个互不相同的数的和，1<=每一个数<=N
这个证明省略，用数学归纳法一下就能出来。

证明了上面，也就说明，1、2、3……N之和必为Ｎ＊（Ｎ　＋ 1） / 2，而Ｎ＊（Ｎ　＋ 1） / 2必为1、2、3……N之和。

根据题目已知条件，1 <= a[i] <= N
将数组求和，与Ｎ＊（Ｎ　＋ 1） / 2比较，不等则说明有重复。（这里又是个证明，妈d，没办法，力求严谨，如果不等又不重复，说明，a[i]只能是从1到N，而从1到N的和只能是Ｎ＊（Ｎ　＋ 1） / 2，矛盾。所以，如果和不等于Ｎ＊（Ｎ　＋ 1） / 2，说明必定有数字重复）

空间复杂度O（1），时间复杂度O（N）-〉求和

#include <vector>
using namespace std;

static const unsigned int N = 100;
bool IsNumberDuplicate(const vector<int>& array) {
int i = 0;
int sum = 0;
while (i++ < N) {
sum += array[i];
}

if (sum != (1 + N) * N / 2) {
return true;
}

return false;

}

这个方法有一点问题啊，开始已经说了。

引用:

作者: zero

注意: 把A[1..N]中的所有项加起来这种办法是行不通的。

比如如果数组大小是4，然后有1, 1, 4, 4, 那么加起来也是10，so...

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式