Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Simple Linear Regression (Least Squares)

Fit the best straight line through data points with the least squares formulas.

Das lernst du

  • Fit a line with closed-form formulas
  • Compute slope and intercept
  • Understand what best fit means

Problem

Übersetzung anzeigen

Linear regression finds the line y = slope × x + intercept that best fits the data, meaning the sum of squared errors is as small as possible. For one input variable there is an exact formula:

  • slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
  • intercept = ȳ - slope × x̄

where x̄ and ȳ are the means of xs and ys. If all xs are equal, return slope 0 and intercept ȳ.

Implement linear_regression(xs, ys).

Input

xs, ys: The x and y values of the data points (same length).

Output

Return [slope, intercept].

Einschränkungen

1 ≤ number of points ≤ 10,000

-10,000 ≤ each value ≤ 10,000

Beispiele

Beispiel 1
Eingabe:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]

Erwartete Ausgabe:
expected = [2.0, 1.0]
Eingabe:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};

Erwartete Ausgabe:
std::vector<double> expected = {2.0, 1.0};
Eingabe:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};

Erwartete Ausgabe:
double[] expected = new double[] {2.0, 1.0};

Erläuterung

The points lie exactly on y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 and Σ(x - x̄)² = 5, so slope = 2 and intercept = 6 - 2 × 2.5 = 1.

Beispiel 2
Eingabe:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]

Erwartete Ausgabe:
expected = [0.5, 1.5]
Eingabe:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};

Erwartete Ausgabe:
std::vector<double> expected = {0.5, 1.5};
Eingabe:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};

Erwartete Ausgabe:
double[] expected = new double[] {0.5, 1.5};

Erläuterung

x̄ = 1 and ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 and Σ(x - x̄)² = 2, so slope = 0.5 and intercept = 2 - 0.5 × 1 = 1.5.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

The best-fit line comes from how x and y vary together around their means.

Hinweis 2

Compute the means first, then accumulate the numerator and denominator for the slope formula.

Hinweis 3

If all x-values are the same, the slope is undefined, so return a flat line through the average y-value.

Erwartete Komplexität

O(n) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.