Codeforces 1512A Spy Detected! 偵測到間諜!!

Klook.com
文章觀看次數: 31

題目說明

難易度 : 800

英文原文如下

You are given an array a consisting of n (n≥3) positive integers. It is known that in this array, all the numbers except one are the same (for example, in the array [4,11,4,4] all numbers except one are equal to 4 ).

Print the index of the element that does not equal others. The numbers in the array are numbered from one.

中文翻譯

給予你一個陣列 a 包含了 n (n≥3) 個正整數。已知的是在這個陣列中，所有的數字除了一個之外都是相同的 (舉例來說，陣列 [4,11,4,4] 中所有的數字除了1 之外其他都是 4 )。

印出與其它者不同的索引。索引從1開始表示。

輸入

The first line contains a single integer t (1≤t≤100). Then t test cases follow.

The first line of each test case contains a single integer n (3≤n≤100) — the length of the array a .

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤100).

It is guaranteed that all the numbers except one in the a array are the same.

第一行包含了一個整數 t (1≤t≤100)。 接下來就有 t 個測試案例。

每個測試案例的第一行包含了一個整數 n (3≤n≤100) — 也就是陣列 a 的長度。

每個測試案例的第二行則包含了 n 個整數 a1,a2,…,an (1≤ai≤100)。

保證了陣列中的所有數字除了一個之外都是相同的。

輸出

For each test case, output a single integer — the index of the element that is not equal to others.

針對每個測試案例，輸出一個整數 — 與其他不相同的元素它的索引。

範例

輸入4
4
11 13 11 11
5
1 4 4 4 4
10
3 3 3 3 10 3 3 3 3 3
3
20 20 10
輸出2
1
5
3

解題思路

相信看到這一題，肯定會有人想到先用Sort，然後取頭尾來判斷吧

Sort後，從頭尾各自去確認確實是可以的。但Sort的這個動作本身就有 O(n log n)的速度，通常不會是最好的

在我們的解答中，我們使用了兩個 for loop來判斷

首先會先將第一個元素當作基準值，然後 for 遇上不一樣時停下，紀錄數字以及其索引

再來第二次的 for 迴圈則是從尾開始，要是其索引不等於上面的索引就可以進行比較

要是該元素的值等於基準值，就代表第一個 for 找到的值就是唯一不同的

要是不相等，就代表著第一個元素本身就是不同於其他元素的

C# 解決方案

方案1

int t = int.Parse(Console.ReadLine());

for(int i=0; i<t; i++){
    int n = int.Parse(Console.ReadLine());
    
    int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    var tmp1 = arr[0];
    var tmp2 = 0;
    
    var tmp2Idx = 0;
    
    for(int j=1; j<arr.Length; j++){
        if(arr[j]!=tmp1){
            tmp2 = arr[j];
            tmp2Idx = j;
            break;
        }
    }
    
    for(int k=arr.Length-1; k>0; k--){
        if(k!=tmp2Idx){
            if(arr[k]==tmp1){
                Console.WriteLine(tmp2Idx+1);
                break;
            }
            else{
                Console.WriteLine(1);
                break;
            }
        }
    }
    
}

時間複雜度 : O(n)

Java 解決方案

方案1

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        scanner.nextLine();
        
        for(int i=0; i<t; i++){
            int n = scanner.nextInt();
            scanner.nextLine();
            
            int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                       .mapToInt(Integer::parseInt)
                       .toArray();
            int tmp1 = arr[0];
            int tmp2 = 0;
            
            int tmp2Idx = 0;
            
            for(int j=1; j<arr.length; j++){
                if(arr[j]!=tmp1){
                    tmp2 = arr[j];
                    tmp2Idx = j;
                    break;
                }
            }
            
            for(int k=arr.length-1; k>0; k--){
                if(k!=tmp2Idx){
                    if(arr[k]==tmp1){
                        System.out.println(tmp2Idx+1);
                        break;
                    }
                    else{
                        System.out.println(1);
                        break;
                    }
                }
            }
            
        }
    }
}

時間複雜度 : O(n)

Klook.com

Python3 解決方案

方案1

t = int(input())

for i in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    tmp1 = arr[0]
    tmp2 = 0
    tmp2Idx = 0
    
    for j in range(1,len(arr)):
        if(arr[j]!=tmp1):
            tmp2 = arr[j];
            tmp2Idx = j;
            break;
    
    for k in range(len(arr)-1, 0, -1):
        if(k!=tmp2Idx):
            if(arr[k]==tmp1):
                print(tmp2Idx+1)
                break
            else:
                print(1)
                break

結論

🧡如果文章有幫上你的忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 1512A – Codeforces

一些其他的Codeforces文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *