时间戳

首页 > 解决方案 > 对数组进行分区

c - 对数组进行分区

问题描述

给定一个包含 n 个元素的随机排序数组 (arr)，函数 partitionArray(int arr[], int n, int x) 将元素划分为两个子集，使得元素 <= x 在左侧子集中，元素 > x 在右侧子集。

测试用例的第一行将包含两个数字 n（列表中的元素数）和 x（用于分区的数字），以空格分隔。下一行将包含 N 个空格分隔的整数。

对于某些情况，我从以下函数中得到错误的输出。

这是我的代码：

void partitionArray(int arr[], int n, int x)
{
    int i, j, temp;
    i = 0;
    j = n-1;
  
    while (i < j)
    {
        while (arr[i] <=x)
            i++;
        while (arr[j] > x)
            j--;
    
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    
        i++;
        j--;
    }  
}

对于我得到正确输出的情况是：

10 6
28 26 25 5 6 7 24 29 6 10

对于我没有得到正确输出的情况是：

10 17
28 26 25 11 16 12 24 29 6 10

The output I am getting in this:

10
6
12
11
25
16
24
29
26
28

Expected Output:

10
6
12
11
16
25
24
29
26
28

10 6
28 26 25 11 5 7 24 29 6 10

The output I am getting in this:

6
25
5
11
26
7
24
29
28
10

Expected Output:

6
5
25
11
26
7
24
29
28
10

谁能帮我这个

标签： c

解决方案

下面的变化会做：

if(i < j){
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

当 j 的值为 i+1 和arr[i]<xand时进行交换时，在 while 循环arr[j]>x之后i++和之后j--，代码中 j 的值为 i-1。因此i<j，在交换之前检查很重要。

假设输入是

2 5
1 10

你的输出将是

10 1

并且必须检查索引，因为索引可能会超出数组的大小。

while (i<n && arr[i]<=x)
    i++;
while (j>=0 && arr[j]>x)
    j--;

示例输入：

5 7
5 3 2 4 1

5 3
7 6 9 5 6

推荐阅读