如何找到newArr[i]在Arr[]中的位置，并在newArr[]中实现此位置-不重复

我希望我在标题中表达得足够清楚，但如果没有，我在这里解释我自己我得到了一个数组从输入(如Arr = {,)。

只能使用1个附加数组(1个原始数组1个附加数组)

这是我目前所做的:我创建了一个名为newArr的新数组，并将Arr包含的所有值赋给它。我对它进行了排序(因为它需要nlogn的时间复杂度)然后将重复项移到末尾。

现在我不明白了:

现在我需要移动原始数字到他们的位置根据主要(数组中的所有值都是正的，它们可以大于
n(数组的大小)，也可以小于n)我还需要返回数组中原始数字的个数原来的数字应该保持在相同的位置，重复的数字在数组的末尾，它们的顺序无关紧要。

不能使用其他数组只能使用当前的数组(2)我一直在考虑做一些二分搜索但是所有的都出错了。(如bin_search_first)和原始二进制文件，但仍然无法管理它。谁能给我点提示吗?

这里是我所在位置的代码


#define _CRT_SECURE_NO_WARNINGS
/*Libraries*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
int* input_array(int);
int moveDuplicatesV2(int*, int);
void merge(int* a, int p, int q, int r);
void merge_sort(int* a, int first, int last); 
void swap(int* v, int* u);
int bin_search_first(int , int* , int );

int main()
{
int arr[10] =  { };
int n = 12; 
int k = 0;
int first = 0;
int last = n - 1;
int mid = (first + last) / 2;
int l = n - 1;
int* D = arr + 1;
int j = 0;
size_t dupes_found = 0;
int* newArr = (int*)malloc(12 * sizeof(int));
assert(newArr);
for (int i = 0; i < n; i++)
{
newArr[i] = arr[i];
}
merge_sort(newArr, first, last);
for (size_t i = 0; i < n - 1 - dupes_found;) 
{
if (newArr[i] == newArr[i + 1])
{
dupes_found++;
int temp = newArr[i];
memmove(&newArr[i], &newArr[i + 1], sizeof(int) * (n - i - 1));
newArr[n - 1] = temp;
}
else {
i++;
}
}
j = 0;
int key = 0;
first = 0;
for (int i = 0; i < n - dupes_found; i++)
{
key = newArr[i];
first = bin_search_first(key, arr,n);
swap(&newArr[i], &newArr[first]);
newArr[first] = newArr[i];

}
for (int i = 0; i < n; i++)
{
arr[i] = newArr[i];
}

for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
return n - dupes_found;
}
void merge(int* a, int p, int q, int r)
{
int i = p, j = q + 1, k = 0;
int* temp = (int*)malloc((r - p + 1) * sizeof(int));
assert(temp);
while ((i <= q) && (j <= r))
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
while (j <= r)
temp[k++] = a[j++];
while (i <= q)
temp[k++] = a[i++];
/* copy temp[] to a[]   */
for (i = p, k = 0; i <= r; i++, k++)
a[i] = temp[k];
free(temp);
}
void merge_sort(int* a, int first, int last)
{
int middle;
if (first < last) {
middle = (first + last) / 2;
merge_sort(a, first, middle);
merge_sort(a, middle + 1, last);
merge(a, first, middle, last);
}
}
void swap(int* v, int* u)
{
int temp;
temp = *v;
*v = *u;
*u = temp;
}
int bin_search_first(int key, int* a, int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2; // low + (high - low) / 2
if (key > a[mid])
low = mid + 1;
else
if (key < a[mid])
high = mid - 1;
else //key==a[mid]
if ((low == high) || (a[mid - 1] < key))
return mid;
else
high = mid - 1;
}
return -1;
}

我的想法是:

排序数组(nlogn)
循环遍历数组，对于每个值，保存指向其第一次出现的指针(n)
循环遍历原始数组，如果该值是第一次出现，则将该值插入结果数组。是否第一次出现可以使用排序数组来检查:这个数组中的每个元素都有一个额外的标志，如果该值已经出现，将设置该标志。因此，使用bsearch搜索元素，如果看到，则附加到结果数组的后面(顺序无关紧要)，如果没有看到，则附加到数组的开头并设置看到的值。(nlogn，因为搜索不需要寻找第一个元素，因为它是预先计算的，所以logn，遍历数组n)

下面是一个示例代码(您可以用归并排序替换qsort，使算法实际上是nlogn，我只是使用qsort，因为它是给定的):

#include <stdio.h>
#include <stdlib.h>
struct arr_value {
int value;
int seen;
struct arr_value *first;
};
int compar(const void *p1,const void *p2) {
struct arr_value *v1 = (struct arr_value *)p1;
struct arr_value *v2 = (struct arr_value *)p2;
if(v1->value < v2->value) {
return -1;
} else if(v1->value == v2->value) {
return 0;
}
return 1;
}
int main()
{
#define NumCount (12)
int arr[NumCount] =  { 7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2 };
int arrResult[NumCount];
int resultCount = 0;
int resultCountBack = 0;
struct arr_value arrseen[NumCount];
for(int i = 0; i < NumCount; ++i) {
arrseen[i].value = arr[i];
arrseen[i].seen = 0;
}

qsort(arrseen, NumCount, sizeof(struct arr_value), compar);

struct arr_value *firstSame = arrseen;
firstSame->first = firstSame;
for(int i = 1; i < NumCount; ++i) {
if(arrseen[i].value != firstSame->value) {
firstSame = arrseen + i;
}
arrseen[i].first = firstSame;
}

struct arr_value key;
for(int i = 0; i < NumCount; ++i) {
key.value = arr[i];
struct arr_value *found = (struct arr_value *)bsearch(&key, arrseen, NumCount, sizeof(struct arr_value), compar);
struct arr_value *first = found->first;

if(first->seen) {
// value already seen, append to back
arrResult[NumCount - 1 - resultCountBack] = first->value;
++resultCountBack;
} else {
// value is new, append
arrResult[resultCount++] = first->value;
first->seen = 1;
}
}

for(int i = 0; i < NumCount; ++i) {
printf("%d ", arrResult[i]);
}
return 0;
}

输出:

7 3 1 2 9 5 6 2 9 2 3 7

首先，memmove不是在固定时间内运行，因此循环

for (size_t i = 0; i < n - 1 - dupes_found;) 
{
if (newArr[i] == newArr[i + 1])
{
dupes_found++;
int temp = newArr[i];
memmove(&newArr[i], &newArr[i + 1], sizeof(int) * (n - i - 1));
newArr[n - 1] = temp;
}
else {
i++;
}
}

驱动时间复杂度为二次元。你必须重新考虑这个方法。

看来你没有抓住关键的一点:

数组中所有的值都是正的

这严重暗示了将值更改为负值是一种方法。

具体来说，当您遍历初始数组并在temp中搜索其元素时，比较_绝对值_。当一个元素在temp中被发现，并且它在那里仍然是正的，将它在temp中的所有副本翻转为负的。否则在initial中翻转。

到目前为止，它是O(n log n)。

然后执行称为stable_partition的算法:将所有正数移动到负数前面，保持顺序。我不能在这里拼出来——我不想剥夺你自己找出答案的乐趣(仍然是O(n log n)

最后把所有消极的东西都变成积极的。

相关内容

最新更新

热门标签：