LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@anonymously115

paizaラーニングレベルアップ問題集の「重複要素の削除」をやってみた。

Posted at

paizaラーニングレベルアップ問題集の重複要素の削除をやってみました。

問題

主に

  • 新たな配列$B$になければ追加
  • 採用済みの要素の集合を用意し、その集合になければ追加

の方法で解いてみたいと思います（$N\le2\times10^5$等の制約がある場合、後者の方が速いです）。
言語によっては、集合が挿入順を保つ場合もあります。

C
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int A[n];
	for (int i = 0; i < n; i++) scanf("%d", &A[i]);
	int B[n];
	int m = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			if (j == m) {
				B[m++] = A[i];
				break;
			} else if (B[j] == A[i]) {
				break;
			}
		}
	}
	for (int i = 0; i < m; i++) printf("%d\n", B[i]);
	return 0;
}

#include <stdio.h>
#include <stdbool.h>

int main() {
	int n;
	scanf("%d", &n);
	int A[n];
	for (int i = 0; i < n; i++) scanf("%d", &A[i]);
	int B[n];
	int m = 0;
	bool S[101] = {};
	for (int i = 0; i < n; i++) {
		if (!S[A[i]]) {
			B[m++] = A[i];
			S[A[i]] = true;
		}
	}
	for (int i = 0; i < m; i++) printf("%d\n", B[i]);
	return 0;
}
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	for (int i = 0; i < n; i++) cin >> A[i];
	vector<int> B;
	for (int i = 0; i < n; i++) if (find(B.begin(), B.end(), A[i]) == B.end()) B.push_back(A[i]);
	for (int b : B) cout << b << endl;
	return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	for (int &a : A) cin >> a;
	vector<int> B;
	unordered_set<int> S;
	for (int a : A) {
		if (!S.count(a)) {
			B.push_back(a);
			S.insert(a);
		}
	}
	for (int b : B) cout << b << endl;
	return 0;
}
C#
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
	public static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		int[] A = new int[n];
		for (int i = 0; i < n; i++) A[i] = int.Parse(Console.ReadLine());
		List<int> B = new List<int>();
		for (int i = 0; i < n; i++) if (!B.Contains(A[i])) B.Add(A[i]);
		foreach (int b in B) Console.WriteLine(b);
	}
}

C#のHashSetは挿入順を保ちます。

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
	public static void Main()
	{
		int[] A = Enumerable.Range(0, int.Parse(Console.ReadLine())).Select(_ => int.Parse(Console.ReadLine())).ToArray();
		HashSet<int> B = new HashSet<int>();
		foreach (int a in A) {
			B.Add(a);
		}
		foreach (int b in B) Console.WriteLine(b);
	}
}

LINQのDistinctメソッドも使えます。

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
	public static void Main()
	{
		int[] A = Enumerable.Range(0, int.Parse(Console.ReadLine())).Select(_ => int.Parse(Console.ReadLine())).ToArray();
		int[] B = A.Distinct().ToArray();
		foreach (int b in B) Console.WriteLine(b);
	}
}
Go
package main
import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	A := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&A[i])
	}
	B := []int{}
	for i := 0; i < n; i++ {
		k := -1
		for j, b := range(B) {
			if b == A[i] {
				k = j
				break
			}
		}
		if k == -1 {
			B = append(B, A[i])
		}
	}
	for _, b := range(B) {
		fmt.Println(b)
	}
}

package main
import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	A := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&A[i])
	}
	B := []int{}
	S := make(map[int]bool)
	for _, a := range(A) {
		if !S[a] {
			B = append(B, a)
			S[a] = true
		}
	}
	for _, b := range(B) {
		fmt.Println(b)
	}
}
Java
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] A = new int[n];
		for (int i = 0; i < n; i++) A[i] = sc.nextInt();
		sc.close();
		List<Integer> B = new ArrayList<>();
		for (int i = 0; i < n; i++) if (!B.contains(A[i])) B.add(A[i]);
		for (int b : B)	System.out.println(b);
	}
}

順序を保持したい場合はLinkedHashSetを使います。

import java.util.*;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = IntStream.range(0, n).map(__ -> sc.nextInt()).toArray();
		sc.close();
		Integer[] A = Arrays.stream(a).boxed().toArray(Integer[]::new);
		Set<Integer> B = new LinkedHashSet<>(Arrays.asList(A));
		for (int b : B) System.out.println(b);
	}
}
JavaScript
const [N, ...A] = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n').map(Number);
const B = [];
for (var i = 0; i < N; i++) if (B.indexOf(A[i]) === -1) B.push(A[i]);
B.forEach(b => console.log(b));

JavaScriptのSetは挿入順を保ちます。

const [N, ...A] = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n').map(Number);
const B = new Set(A);
B.forEach(b => console.log(b));
Kotlin
fun main() {
	val n = readLine()!!.toInt()
	val A = Array(n) { readLine()!!.toInt() }
	val B: MutableList<Int> = mutableListOf()
	for (i in 0 until n) if (!B.contains(A[i])) B.add(A[i])
	for (b in B) println(b)
}

KotlinのMutableSetは挿入順を保ちます。

fun main() {
	val A = Array(readLine()!!.toInt()) { readLine()!!.toInt() }
	val B: MutableSet<Int> = mutableSetOf()
	for (a in A) B.add(a)
	for (b in B) println(b)
}
PHP
<?php
	$n = intval(fgets(STDIN));
	$A = [];
	for ($i = 0; $i < $n; $i++) $A[] = intval(fgets(STDIN));
	$B = [];
	for ($i = 0; $i < $n; $i++) if (!in_array($A[$i], $B)) $B[] = $A[$i];
	foreach ($B as $b) echo $b, PHP_EOL;
?>

<?php
	$n = intval(fgets(STDIN));
	$A = [];
	for ($i = 0; $i < $n; $i++) $A[] = intval(fgets(STDIN));
	$B = array_unique($A);
	foreach ($B as $b) echo $b, PHP_EOL;
?>
Perl
my $n = int(<STDIN>);
my @A;
for (1..$n) {
	push @A, int(<STDIN>);
}
my @B;
for (my $i = 0; $i < $n; $i++) {
	for (my $j = 0; $j <= scalar(@B); $j++) {
		if ($j == scalar(@B)) {
			push @B, $A[$i];
			last;
		} else {
			last if $B[$j] == $A[$i];
		}
	}
}
for $b (@B) {
	print "$b$/";
}

my $n = int(<STDIN>);
my @A;
for (1..$n) {
	push @A, int(<STDIN>);
}
my %S;
my @B = grep { !$S{$_}++ } @A;
for $b (@B) {
	print "$b$/";
}
Python3
n = int(input())
A = [int(input()) for _ in range(n)]
B = [A[i] for i in range(n) if A[i] not in A[:i]]
for b in B:
	print(b)

n = int(input())
A = [int(input()) for _ in range(n)]
B = []
S = set()
for a in A:
	if a not in S:
		B.append(a)
		S.add(a)
for b in B:
	print(b)
Ruby
N = gets.to_i
A = N.times.map { gets.to_i }
B = []
N.times do |i|
	if !B.include?(A[i])
		B << A[i]
	end
end
B.each do |b|
	p b
end

N = gets.to_i
A = N.times.map { gets.to_i }
B = A.uniq
B.each do |b|
	p b
end
Scala
import scala.io.StdIn._
import scala.collection.mutable._

object Main extends App{
	val n = readInt()
	val A = (0 until n).map { _ => readInt() }
	val B: ListBuffer[Int] = ListBuffer()
	for (i <- 0 until n) if (!B.contains(A(i))) B += A(i)
	for (b <- B) println(b)
}

import scala.io.StdIn._
import scala.collection.mutable._

object Main extends App{
	val n = readInt()
	val A = (0 until n).map { _ => readInt() }
	val B: ListBuffer[Int] = ListBuffer()
	val S: Set[Int] = Set()
	for (i <- 0 until n) {
		if (!S.contains(A(i))) {
			B += A(i)
			S.add(A(i))
		}
	}
	for (b <- B) println(b)
}
Swift
let n = Int(readLine()!)!
let A = (0..<n).map { _ in Int(readLine()!)! }
var B: [Int] = []
for i in 0..<n {
	if B.firstIndex(of: A[i]) == nil {
		B.append(A[i])
	}
}
for b in B {
	print(b)
}

let n = Int(readLine()!)!
let A = (0..<n).map { _ in Int(readLine()!)! }
var B: [Int] = []
var S: Set<Int> = []
for i in 0..<n {
	if !S.contains(A[i]) {
		B.append(A[i])
		S.insert(A[i])
	}
}
for b in B {
	print(b)
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?