Kleinste positive Zahl in einem Array

3 Lösungen

#341

Fortgeschrittener - C# von JKooP - 21.11.2020 um 11:42 Uhr

Gegeben sei ein (beliebig großes) unsortiertes Integer- Array welches sowohl aus positiven als auch negativen Zahlen besteht.
Ermittelt werden soll die erste fehlende positive Zahl im Array.

Beispiele:
arr = [1, 2, 0] sortiert: [0, 1, 2]
Lösung: 3

arr = [5, 4, -2, -1, 1] sortiert: [-2, -1, 1, 4, 5]
Lösung: 2

arr = [6, 7, 8, 9, 10]
Lösung: 1

arr = [-4, -2, -1]
Lösung: 1

arr = [1, 2, 3, 4, 2147483647, 8]
Lösung: 5

arr = []
Lösung: 1

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von AchtungHuPe (170 Punkte) - 29.12.2020 um 22:05 Uhr

C#-Code

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

namespace ErsteFehlendeZahl_341
{
    class Program
    {
        static void Main(string[] args) 
        {
            var arr = new int[] { 1, 2, 0 };

            // Array optimieren: Nur positive Zahlen, jede Zahl kommt nur 1x vor
            Array.Sort(arr);
            var workArr = new List<int>();
            for (var i=0; i < arr.Length; i++)
            {
                if (arr[i] > 0 && !workArr.Contains(arr[i]) )
                    workArr.Add(arr[i]);
            }

            AnalyseList(workArr);
        }

        public static void PromptSolution(int missing)
        {
            Console.WriteLine($"Die erste fehlene Zahl ist '" + missing + "'");
            Console.ReadLine();
        }

        public static void AnalyseList(List<int> _workArr)
        {
            int solution = 0;

            // Spezialfälle wo das Ergebnis sofort feststeht
            if (_workArr.Count() == 0 || _workArr[0] > 1)
                solution = 1;
            else
            // Suche die Lücke
            {
                for (int i = 0; i < _workArr.Count(); i++)
                {
                    if (i + 1 != _workArr[i])
                    {
                        solution = i + 1;
                        break;
                    }
                    // i++;
                }

                // Letze Möglichkeit:
                if (solution == 0)
                    solution = _workArr.Last() + 1;
            }

            PromptSolution(solution);
        }

    }
}