iT邦幫忙

4

[Google Code Jam] C++ Trouble Sort 麻煩排序

前言

這是Google的第二題,這題跟上一題比起來簡易了許多,主要使用排序功能。
我國文造詣真的很差,打篇文章都筆寫程式還久了有點慘...請見諒。
原題目

題目

Code Jam仔細研究了經典的泡沫排序法,然而發現了一個新的變種。
正常的泡沫排序法是檢查相鄰的數字,如果左邊大於現在的數字,則交換。但是我們的算法是三個相鄰的數字,如果左邊數字大於右邊數字,則翻轉整組,因此我們將"三個一組泡沫排序"命名為Trouble Sort。
例如,L = 5 6 6 4 3,Trouble Sort排序如下:

  • 第一關:
    • 檢查5 6 6,無動作: 5 6 6 4 3
    • 檢查6 6 4,6 > 4,反轉: 5 4 6 6 3
    • 檢查6 6 3,6 > 3,反轉: 5 4 3 6 6
  • 第二關:
    • 檢查5 4 3,5 > 3,反轉: 3 4 5 6 6
    • 檢查4 5 6,無動作: 3 4 5 6 6
    • 檢查5 6 6,無動作: 3 4 5 6 6
  • 第三遍檢查,因為都無動作所以結束。
    我們期待在夏威夷上的排綠會議展示Trouble Sort,但我們實習生指出了一個問題:Trouble Sort可能沒有正確排序!例如,8 9 7。
    我們需要您的幫助進一步研究。給N個整數列表,確認Trouble Sort是否能成功將列表中的整數排序為非遞減排序。如果不能,則找到第一格排序錯誤的索引(從0開始):就是第一個值大於前面的值。

輸入

輸入的第一行T測試筆數。每個測試筆數有兩行組成:一行整數N,列表中的大小,然後另一行帶有個N個整數V。

輸出

輸出每筆資料,包含Case #x: y,其中x是測試筆數編號,如果是正確排序y輸出OK,如果不是則輸出第一個錯誤的索引(從0開始)。

範圍

1 <= Ť <= 100 。
1 <= V <= pow(10,9)。
測資1: 3 <= N <=100 每個測試集10秒。
測資2: 3 <= N <= pow(10,5) 每個測試集20秒。
記憶體限制:1GB。

範例

輸入:
2
5
5 6 8 4 3
3
8 9 7

輸出:
Case #1: OK
Case #2: 1

解析

  1. 由上述範例可知道我們比較都是隔一個來比較,而大於右邊則翻轉,翻轉其實是最左最右交換。
  2. 奇數索引不會影響到偶數索引則可分為2個數列,奇數索引數列和偶數索引數列,將其排序。
  3. 排序後將兩組合併放回原本的位置上,即可得到答案。

程式碼

做了STL版本和指標版本,測試看Google測資輸出會不會有問題,很幸運的Google的都可以使用。
1.STL版本

#include <iostream>
#include <vector>
#include <algorithm>
#include "math.h"

using namespace std;

// 輸出
void Print(const int& index, const int& result)
{
	if (result == -1)
	{
		cout << "Case #" << index + 1 << ": OK" << endl;
	}
	else
	{
		cout << "Case #" << index + 1 << ": " << result << endl;
	}
}

// num1: 奇數數列
// num1: 偶數數列
int Compute(vector<int>& num1, vector<int>& num2)
{
    // 直接對奇數和偶數排序,可換成自己實作排序(O(N^2)應該是不能)。
	sort(num1.begin(), num1.end());
	sort(num2.begin(), num2.end());
	int nowNum = num1[0];
    
    // 檢查奇數索引和偶數索引兩個相鄰,是否是非遞減,若不是則回傳索引位置。
    // 依照num2的大小來取得索引, 所以要乘上2才是原本索引位置。
    // 為何回傳上一個索引位置? 因我們是用上一個數字來比較,反之用下一個比較則傳回當下索引
	for (size_t index = 0; index < num2.size(); index++)
	{
		if (nowNum > num1[index])
		{
			return (index << 1) - 1;
		}

		if (num1[index] > num2[index])
		{
			return (index << 1);
		}
		nowNum = num2[index];
	}

    // num1可能會比num2多一個數字,若小於上一個數字則回傳上一個索引位置。
    // 索引位置num1大小乘上2 - 2為最大索引(因為num2少1所以要多減1),回傳上一個,所以減3
	if (num1.size() > num2.size()
		&& nowNum > num1[num1.size() - 1])
	{
		return (num1.size() << 1) - 3;
	}

	return -1;
}

// 輸入
void Input()
{
    //筆數
	int testCount = 0;
    
	while (cin >> testCount)
	{
		for (int count = 0; count < testCount; count++)
		{
            // 數列長度
			int numSize;
			cin >> numSize;
			vector<int> num1(static_cast<unsigned int>(ceil(numSize / 2.0)));
			vector<int> num2(static_cast<unsigned int>(floor(numSize / 2.0)));
            
            // 輸入奇偶數列
			for (size_t index = 0; index < num2.size(); index++)
			{
				cin >> num1[index] >> num2[index];
			}
            
            // 奇數可能多一個
			if (num1.size() > num2.size())
			{
				cin >> num1[num1.size() - 1];
			}

			int result = Compute(num1, num2);

			Print(count, result);
		}
	}
}

int main()
{
	Input();
	return 0;
}

2.指標版本

#include <iostream>
#include <algorithm>
#include "math.h"

using namespace std;

// 輸出
void Print(const int& index, const int& result)
{
	if (result == -1)
	{
		cout << "Case #" << index + 1 << ": OK" << endl;
	}
	else
	{
		cout << "Case #" << index + 1 << ": " << result << endl;
	}
}

// num1: 奇數數列
// num1: 偶數數列
// num1Size: num1大小
// num2Size: num2大小
int Compute(int*& num1, int*& num2, unsigned int num1Size, unsigned int num2Size)
{
    // 直接對奇數和偶數排序,可換成自己實作排序(O(N^2)應該是不能)。
	sort(num1, num1 + num1Size);
	sort(num2, num2 + num2Size);
	int nowNum = num1[0];
    
    // 檢查奇數索引和偶數索引兩個相鄰,是否是非遞減,若不是則回傳索引位置。
    // 依照num2的大小來取得索引, 所以要乘上2才是原本索引位置。
    // 檢查到則回傳上一個索引位置,因我們是用上一個數字來比較,反之用下一個比較則傳回當下索引
	for (unsigned int index = 0; index < num2Size; index++)
	{
		if (nowNum > num1[index])
		{
			return (index << 1) - 1;
		}

		if (num1[index] > num2[index])
		{
			return (index << 1);
		}
		nowNum = num2[index];
	}

    // num1可能會比num2多一個數字,若小於上一個數字則回傳上一個索引位置。
    // 索引位置num1大小乘上2 - 2為最大索引(因為num2少1所以要多減1),回傳上一個,所以減3
	if (num1Size > num2Size
		&& nowNum > num1[num1Size - 1])
	{
		return (num1Size << 1) - 3;

	}

	return -1;
}

// 刪除指標
template <class T>
inline void DeleteArray(T& ptr)
{
	delete[] ptr;
	ptr = nullptr;
}

// 輸入
void Input()
{
    //筆數
	int testCount = 0;
    
	while (cin >> testCount)
	{
		for (int count = 0; count < testCount; count++)
		{
            // 數列長度
			int numSize;
			cin >> numSize;
            
			unsigned int num1Size = static_cast<unsigned int>(ceil(numSize / 2.0));
			unsigned int num2Size = static_cast<unsigned int>(floor(numSize / 2.0));
			int* num1 = new int[num1Size];
			int* num2 = new int[num2Size];
            
            // 輸入奇偶數列
			for (unsigned int index = 0; index < num2Size; index++)
			{
				cin >> num1[index] >> num2[index];
			}
            
            // 奇數可能多一個
			if (num1Size > num2Size)
			{
				cin >> num1[num2Size - 1];
			}

			int result = Compute(num1, num2);
            
            DeleteArray(num1);
			DeleteArray(num2);
            
			Print(count, result);
		}
	}
}

int main()
{
	Input();
	return 0;
}

結果

https://ithelp.ithome.com.tw/upload/images/20180708/20110564PTyc5vWPgH.png

以上兩個版本看起來其實大同小異,對於我來說指標版本方便在可以控制神麼時候要釋放記憶體,這裡在result後就釋放掉記憶體了,vector部分則要等到Print跑完,如果認知有誤或還有更好算法希望大大們指導提供。


2 則留言

1
fysh711426
iT邦新手 1 級 ‧ 2018-07-16 03:38:10

這題的解法和大大類似,將奇數項和偶數項分開排序,並偷懶用 STL 的 sort,您程式內提到的實作排序 O(n²),小弟就是血淋淋的例子,大 Case 會超時。
/images/emoticon/emoticon16.gif

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
    int c = 0;
    int testcase;
    scanf("%d", &testcase);

    while (testcase--)
    {
        int N, T;
        scanf("%d", &N);

        vector<int> nums1; //奇數陣列
        vector<int> nums2; //偶數陣列

        //讀取陣列
        nums1.reserve(N / 2);
        nums2.reserve(N / 2);
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &T);
            if (i % 2 == 0)
                nums1.push_back(T);
            else
                nums2.push_back(T);
        }

        //排序
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        //檢查排序是否成功
        int curr, prev = -1;
        int index = -1;
        for (int i = 0; i < N; i++)
        {
            curr = i % 2 == 0 ? nums1[i / 2] : nums2[i / 2];
            if (prev > curr)
            {
                index = i - 1;
                break;
            }
            prev = curr;
        }

        //印出結果
        if (index == -1)
        {
            printf("Case #%d: OK\n", c + 1);
        }
        else
        {
            printf("Case #%d: %d\n", c + 1, index);
        }

        c++;
    }

    //system("pause");
    return 0;
}
1
神Q超人
iT邦新手 4 級 ‧ 2018-07-16 19:33:15

這個我的方式也很大大一樣,
奇數和偶數拆開來排序,
雖然我排序也直接用函數,但大小CASE都會過不知道為什麼/images/emoticon/emoticon16.gif

#會先輸入總共有幾題
questionCount = int(input())
#跑迴圈
for index in range(1,questionCount + 1):
    #這邊會輸入陣列的行數,
    #我們複製一個暫存的空陣列,等等裝排序後的資料
    tempArr = [None] * int(input())
    '''
    這邊把輸入的內容用split切成陣列,
    之後用map做陣列的尋訪,把每個值都轉成數字,
    最後再用list把它轉換成陣列
    '''
    arr = list(map(int, input().split(" ")))
    #把奇數排列後的資料裝到tempArr的奇數位置
    tempArr[0::2] = sorted(arr[0::2])
    #把偶數排列後的資料裝到tempArr的偶數位置
    tempArr[1::2] = sorted(arr[1::2])
    
    #印出的function
    def printStatus(status):
        print("Case #" + str(index) + ": " + status)
    
    #這邊設定預設結果為OK,如果再迴圈內沒比較到錯誤的就印出OK
    status = "OK"
    #去檢查我們剛剛用來放奇偶數各自排列的暫存陣列
    for i in range(len(tempArr)-1):
        #如果這次的數字比下一個數字大代表沒有排好
        if(tempArr[i]>tempArr[i+1]):
            #所以把錯誤的位置放到status中跳出迴圈
            status = str(i)
            break
    #把結果印出來
    printStatus(status)

我要留言

立即登入留言